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.

4 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

3 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)

1 Like
#6

We can also solve the problem by using map !!

3 Likes
#7

#include <bits/stdc++.h>

using namespace std;

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

int main() 
{
int t;
cin >> t;
while(t--)
{
	solve();
}
return 0;

}