admin管理员组文章数量:1530040
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 11, 22, 33, 44, so two of them specialize in the 22-nd subject and other two in the 33-rd. The total sum is 6+6+5+5=226+6+5+5=22.
In the second example it's optimal to choose candidates 11, 22 and 55. One person in each subject and the total sum is 6+6+11=236+6+11=23.
In the third example it's impossible to obtain a non-negative sum.
题意:
m个人,n组数据id val ,一个人可以对应多个val,可能为负数,也可能为正数,在n组数据任意选择
满足:最后val和大于0,满足不了输出0,每一个id选择次数相同。求选择最大的val和
分析:
这题开一个vector[N],相应的保存一下每一个id的数据,然后排序
id val
1 8
2 10 9
3 18 15 12
然后,就得借助前缀和这个东西了
id val
1 8
2 10 19
3 18 33 45
人数 1 2 3
36 42 45
然后我竟然在for循环这里完蛋了,
我是先枚举的id的最大size(),即最大人数,然后在枚举的选择人数,
然后就一直WA,做到崩溃。
最后发现,竟然在比较函数应该x>y,不因该写x>=y
但是改了之后就超时了
for循环修改为如下代码:
#include<cstdio>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<functional>
#include<cstring>
#include<string>
#include<cstdlib>
#include<iomanip>
#include<numeric>
#include<cctype>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<list>
#include<set>
#include<map>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define sd(n) scanf("%d",&n)
#define sll(n) scanf("%lld",&n)
#define pd(n) scanf("%d\n",n)
#define pll(n) scanf("%lld\n",n)
#define MAX 26
const int N=1e5+10;
typedef long long ll;
const ll mod=1e9+7;
ll n,m;
ll a[N];
vector<ll>v[N];
ll sum[N];
bool cmp(int x,int y)
{
return x>y;
}
int main()
{
//string s;
//cin>>s;
scanf("%lld%lld",&n,&m);
ll num=0;int maxx=0;
for(int i=1;i<=n;i++)
{
ll x,y;
scanf("%lld%lld",&x,&y);
v[x].push_back(y);
a[x]+=y;
}
for(int i=1;i<=m;i++)
{
sort(v[i].begin(),v[i].end(),cmp);
for(int j=1;j<v[i].size();j++)
{
v[i][j]+=v[i][j-1];
}
maxx=max(maxx,(int)v[i].size());
}
ll ans=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];
ans=max(sum[j],ans);
}
v[i].clear();
}
printf("%lld\n",ans);
return 0;
}
纪念一下:
TLE 20
#include<cstdio>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<functional>
#include<cstring>
#include<string>
#include<cstdlib>
#include<iomanip>
#include<numeric>
#include<cctype>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<list>
#include<set>
#include<map>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define sd(n) scanf("%d",&n)
#define sll(n) scanf("%lld",&n)
#define pd(n) scanf("%d\n",n)
#define pll(n) scanf("%lld\n",n)
#define MAX 26
const int N=1e5+10;
typedef long long ll;
const ll mod=1e9+7;
int n,m;
vector<ll>v[N];
bool cmp(int x,int y)
{
return x>y;
}
int main()
{
//string s;
//cin>>s;
scanf("%d%d",&n,&m);
ll num=0;int maxx=0;
for(int i=1;i<=n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
v[x].push_back(y);
}
for(int i=1;i<=m;i++)
{
sort(v[i].begin(),v[i].end(),cmp);
for(int j=1;j<v[i].size();j++)
{
v[i][j]+=v[i][j-1];
}
maxx=max(maxx,(int)v[i].size());
}
int sum=0;
int ans=0;
for(int j=0;j<maxx;j++)
{
sum=0;
for(int i=1;i<=m;i++)
{
if(j>=v[i].size())
{
continue;
}
//cout<<i<<" "<<v[i][j]<<endl;
if(v[i][j]>0)
sum+=v[i][j];
ans=max(ans,sum);
}
}
printf("%d\n",ans);
return 0;
}
本文标签: codeforcesMulticompetitionSubject
版权声明:本文标题:CodeForces - 1082C . Multi-Subject Competition 好题+差一点 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dianzi/1726693555a1080938.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论