WATSCORE - Editorial

editorial
, , , , ,
#1

PROBLEM LINK:

Practice
Contest, div. 1
Contest, div. 2

Author: Abhishek Pandey
Tester: Ildar Gainullin
Editorialist: Oleksandr Kulkov

DIFFICULTY:
CAKEWALK
PREREQUISITES:
None
PROBLEM:
You’re given N pairs of integers (p_i, s_i) where 1 \leq p_i \leq 11. For each p_i<9 calculate maximum number of s_i with this p_i and output the sum of these numbers.
QUICK EXPLANATION:
You should basically do what’s written in the statement.
EXPLANATION:
Maintain array mx with maximum scores for each problem and output the sum of first 9 elements.

void solve() {
	int n;
	cin >> n;
	vector<int> mx(11);
	for(int i = 0; i < n; i++) {
		int p, s;
		cin >> p >> s;
		mx[p] = max(mx[p], s);
	}
	cout << accumulate(begin(mx), begin(mx) + 9, 0LL) << endl;
}

AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.

3 Likes
#2

what is the use of accumulate…is it any function or algo?

#3

https://en.cppreference.com/w/cpp/algorithm/accumulate

I’m all for asking doubts but please google it first too :slight_smile:

1 Like
#4

Here is my code

2 Likes
#5 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
	int t;
	cin >> t;
	while(t--) {
		int n;
		cin >> n;
		int p[n], s[n];
		for(int i = 0; i < n; i++) {
			cin >> p[i] >> s[i];
		}
		int ans[9] = {0};
		for(int i = 0; i < n; i++) {
			if(p[i] < 9) {
				ans[p[i] - 1] = max(ans[p[i] - 1], s[i]);
			}
		}
		ll sum = 0;
		for(int i = 0; i < 9; i++) {
			sum += ans[i];
		}
		cout << sum << endl;
	}
}

I didn’t use any fancy thing like “accumulate” I just kept an array of the problem type and the max score O(n)

#6

We can also solve the problem by using map !!