CD001 - Editorial

PROBLEM LINK:

Practice
Div-2 Contest

Author: Dharanendra L V
Tester: Dharanendra L V
Editorialist: Dharanendra L V

DIFFICULTY:

Easy

PREREQUISITES:

None.

PROBLEM:

Given an integer N i.e. the number of football matches, and every match from 1 to N has two corresponding integers i.e. S_{i} and R_{i}. The enjoyment you get from a particular match is the product of its stadium’s R_{j} and the number of distinct stadium numbers you’ve watched till now (including the current match’s stadium). The task is to find the order which maximizes the sum of the Enjoyment you get from all the N matches. Output this maximum sum possible.

EXPLANATION:

Initially sort the given pair of S_{i} and R_{i} in the ascending order, according to R_{i} value. And for every distinct value of S_{i} find the enjoyment value after that find the enjoyment values for the remaining mathes and print the value of sum at the end.

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;

bool comp(pair<int, int> a, pair<int, int> b) {

	if(a.second > b.second) return false;
	return true;
}

int main() {

	int t;
	cin >> t;

	while(t--) {

		int n;
		cin >> n;

		vector<pair<int, int> > vect;

		for(int i = 0; i < n; i++) {

			int a, b; cin >> a >> b;
			vect.push_back({a, b});
		}

		sort(vect.begin(), vect.end(), comp);

		set<int> s;
		vector<pair<int, int> > mp;
		long long ans = 0;
		for(int i = 0; i < n; i++) {
			
			if(s.find(vect[i].first) == s.end()) {
				s.insert(vect[i].first);
			}
			else {
				mp.push_back({vect[i].first, vect[i].second});
				continue;
			}
			ans += (s.size() * vect[i].second);
		}

		for(int i = 0; i < mp.size(); i++) {

			ans += (s.size() * mp[i].second);
		}
		cout << ans << endl;
	}

	return 0;
}

Feel free to share your approach here. Suggestions are always welcomed. :slight_smile: