本文主要是介绍Educational Codeforces Round 55 (Rated for Div. 2) C. Multi-Subject Competition，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：
http://codeforces.com/contest/1082/problem/C
C. Multi-Subject Competition
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
A multi-subject competition is coming! The competition has mm different subjects participants can choose from. That's why Alex (the coach) should form a competition delegation among his students.
He has nn candidates. For the ii-th person he knows subject sisi the candidate specializes in and riri — a skill level in his specialization (this level can be negative!).
The rules of the competition require each delegation to choose some subset of subjects they will participate in. The only restriction is that the number of students from the team participating in each of the chosen subjects should be the same.
Alex decided that each candidate would participate only in the subject he specializes in. Now Alex wonders whom he has to choose to maximize the total sum of skill levels of all delegates, or just skip the competition this year if every valid non-empty delegation has negative sum.
(Of course, Alex doesn't have any spare money so each delegate he chooses must participate in the competition).
Input
The first line contains two integers nn and mm (1≤n≤1051≤n≤105, 1≤m≤1051≤m≤105) — the number of candidates and the number of subjects.
The next nn lines contains two integers per line: sisi and riri (1≤si≤m1≤si≤m, −104≤ri≤104−104≤ri≤104) — the subject of specialization and the skill level of the ii-th candidate.
Output
Print the single integer — the maximum total sum of skills of delegates who form a valid delegation (according to rules above) or 00 if every valid non-empty delegation has negative sum.
Examples
input
Copy
6 3 2 6 3 6 2 5 3 5 1 9 3 1
output
Copy
22
input
Copy
5 3 2 6 3 6 2 5 3 5 1 11
output
Copy
23
input
Copy
5 2 1 -1 1 -5 2 -1 2 -1 1 -10
output
Copy
0
Note
In the first example it's optimal to choose candidates 1, 2, 3, 4, so two of them specialize in the 2-nd subject and other two in the 3-rd. The total sum is 6+6+5+5=22.
In the second example it's optimal to choose candidates 1, 2 and 5. One person in each subject and the total sum is 6+6+11=23
In the third example it's impossible to obtain a non-negative sum.
题目大意：
有n个人，m课目
对每个人知道你哪一个课id的专业化水平val
求：每科参加人数相同时的最大专业化水平和
思路：
对每门课能够参加的人的专业化水平从大到小排序
计算每个科目学生水平的前缀和，计算相同参加人数相同的最大技能水平和
对样例1图解：
求sum[]中的最大值
This is the code
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1e5+10;
vector<int> v[N];
int sum[N];
int n,m;
int main()
{int id,val;while(~scanf("%d%d",&n,&m)){memset(sum,0,sizeof(sum));for(int i=1; i<=n; i++){scanf("%d%d",&id,&val);v[id].push_back(val);}for(int i=1; i<=m; ++i)//对每一门课的专业水平从大到小排序sort(v[i].begin(),v[i].end(),greater<int>());//默认从大到小//sort(v[i].begin(),v[i].end(),less<int>());//默认从小到大for(int i=1; i<=m; ++i)//计算前缀和for(int j=1; j<v[i].size(); ++j)v[i][j]+=v[i][j-1];int cnt=0;for(int i=1; i<=m; ++i){for(int j=0; j<v[i].size(); ++j){if(v[i][j]>0)sum[j]+=v[i][j];cnt=max(cnt,sum[j]);}v[i].clear();}printf("%d\n",cnt);}return 0;
}
这篇关于Educational Codeforces Round 55 (Rated for Div. 2) C. Multi-Subject Competition的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
