Codeforces 1082C Multi-Subject Competition 前缀和 A
Codeforces 1082C Multi-Subject Competition
https://vjudge.net/problem/CodeForces-1082C
题目：
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 teamparticipating 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 nnand mm (1≤n≤105, 1≤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≤m, −104≤ri≤104) — the subject of specialization and the skill level of the ii-th candidate.
Output
Examples
Input1
6 3
2 6
3 6
2 5
3 5
1 9
3 1 Output1
22
Input2
5 3 2 6 3 6 2 5 3 5 1 11
Output2
23 Input3
5 2
1 -1
1 -5
2 -1
2 -1
1 -10 Output3
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.
分析：
题目不复杂，很轻松就打出来了，wa了几次调了调bug，然后就TLE到死
本来以为前缀和绝对绝对会超时，所以简单暴力了，，，，
结果标答就是前缀和，真香
TLE代码：
#include <stdio.h> #include <math.h> #include <string.h> #include <algorithm> #include <iostream> #include <string> #include <time.h> #include <queue> #include <string.h> #include <list> #define sf scanf #define pf printf #define lf double #define ll long long #define p123 printf("123\n"); #define pn printf("\n"); #define pk printf(" "); #define p(n) printf("%d",n); #define pln(n) printf("%d\n",n); #define s(n) scanf("%d",&n); #define ss(n) scanf("%s",n); #define ps(n) printf("%s",n); #define sld(n) scanf("%lld",&n); #define pld(n) printf("%lld",n); #define slf(n) scanf("%lf",&n); #define plf(n) printf("%lf",n); #define sc(n) scanf("%c",&n); #define pc(n) printf("%c",n); #define gc getchar(); #define re(n,a) memset(n,a,sizeof(n)); #define len(a) strlen(a) #define f(i,n) for(int i = 0; i < n; i ++) #define LL long long #define eps (1e-6) using namespace std; struct A{ int s; int t; }a[1000000]; bool cmp(A a,A b){ if(a.s < b.s)return true; if(a.s == b.s && a.t > b.t)return true; return false; } int kind[1000000]; int main(){ re(kind,0); int n,m; s(n) s(m) int kinds = 0; f(i,n){ s(a[i].s) s(a[i].t) kind[a[i].s] ++; if(kinds < kind[a[i].s]){ kinds = kind[a[i].s]; } } //p(kinds) if(kinds >= n-20 && n > 10000){ int sum00 = 0; f(i,n){ if(a[i].t >= 0){ sum00 += a[i].t; } } p(sum00) pn return 0; } sort(a,a+n,cmp); int maxi = 0; for(int i = kinds; i >= 1; i --){ int num = 1; while(kind[num] < i){ num ++; } int count0 = i; int sum = 0; int sum0 = 0; f(j,n){ if(a[j].s == num && count0 != 0){ //p(a[j].s) pk p(a[j].t) pn if(a[j].t < 0 && count0 == i){ num ++; while(kind[num] < i){ num ++; } continue; } sum0 += a[j].t; count0 --; } if(count0 == 0){ if(sum0 >= 0){ sum += sum0; } sum0 = 0; num ++; while(kind[num] < i){ num ++; } count0 = i; } } //p(sum) pn if(maxi < sum){ maxi = sum; } //pn } p(maxi) pn return 0; }
1082C - Multi-Subject Competition
At first, it's optimal to take candidates with maximal levels for a fixed subject.
At second, if we fix number of participants in each subject for some delegation, then it's always optimal to choose all subjects with positive sum of levels.
It leads us to a following solution. Let's divide all candidates by it's sisi and sort each group in non-increasing order.
In result we can just iterate over all prefix sums for each group and update global answer of current length with current sum if it has a positive value.
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 5 #define sz(a) int((a).size()) 6 7 int n, m; 8 vector<int> s, r; 9 10 inline bool read() { 11 if(!(cin >> n >> m)) 12 return false; 13 s.assign(n, 0); 14 r.assign(n, 0); 15 16 fore(i, 0, n) { 17 assert(cin >> s[i] >> r[i]); 18 s[i]--; 19 } 20 return true; 21 } 22 23 vector< vector<int> > subs; 24 25 inline void solve() { 26 subs.assign(m + 1, vector<int>()); 27 28 fore(i, 0, n) 29 subs[s[i]].push_back(r[i]); 30 31 fore(id, 0, sz(subs)) { 32 sort(subs[id].begin(), subs[id].end()); 33 reverse(subs[id].begin(), subs[id].end()); 34 } 35 36 vector<int> mx(n + 5, 0); 37 fore(id, 0, sz(subs)) { 38 int curSum = 0; 39 fore(i, 0, sz(subs[id])) { 40 curSum += subs[id][i]; 41 if(curSum < 0) 42 break; 43 44 mx[i + 1] += curSum; 45 } 46 } 47 48 cout << *max_element(mx.begin(), mx.end()) << endl; 49 } 50 51 int main() { 52 #ifdef _DEBUG 53 freopen("input.txt", "r", stdin); 54 int tt = clock(); 55 #endif 56 cout << fixed << setprecision(15); 57 58 if(read()) { 59 solve(); 60 61 #ifdef _DEBUG 62 cerr << "TIME = " << clock() - tt << endl; 63 tt = clock(); 64 #endif 65 } 66 return 0; 67 }
阿里巴巴稳定性 75人发布
投递阿里巴巴等公司10个岗位