| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 18150 |
2016-01-25T00:39:26 Z |
comet |
Schools (IZhO13_school) |
C++14 |
|
40 ms |
5852 KB |
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cassert>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pp;
int N,M,S;
struct school{
ll a,b;
}s[100001];
priority_queue <pp> Q1,Q2;
int main(){
scanf("%d%d%d",&N,&M,&S);
for(int i=0;i<N;i++){
scanf("%lld%lld",&s[i].a,&s[i].b);
}
ll sum=0;
sort(s,s+N,[&](const school& x,const school& y){
return x.a>y.a;
});
/*
for(int i=0;i<N;i++){
printf("%lld %lld\n",s[i].a,s[i].b);
}
puts("-----------------");
*/
for(int i=0;i<N;i++){
// printf("(%lld,%lld)\n",s[i].a,s[i].b);
if(M){
// puts("get A");
sum+=s[i].a;
Q1.push(pp(s[i].b-s[i].a,i));
M--;
} else{
if(!Q1.empty()){ // M overflows
int w=Q1.top().first;
int v=Q1.top().second;
if(S){ // S has margin
if(w+s[i].a>s[i].b){ // revoke is good
// puts("Change old A to B and get new A");
sum+=w+s[i].a;
Q1.pop();
Q1.push(pp(s[i].b-s[i].a,i));
Q2.push(pp(-s[v].b,v));
S--;
} else{ // revoke isn't good
// puts("get B");
sum+=s[i].b;
Q2.push(pp(-s[i].b,i));
S--;
}
} else{
if(!Q2.empty()){ // M and S both overflow
int c=Q2.top().first;
int v2=Q2.top().second;
if(c+w+s[i].a>=s[i].b+c && c+w+s[i].a>0){ // revoke S and M is good
// puts("Change old A to B and discard bad B and get A");
sum+=c+w+s[i].a;
Q1.pop();
Q2.pop();
Q1.push(pp(s[i].b-s[i].a,i));
Q2.push(pp(-s[v].b,v));
} else if(c+w+s[i].a<s[i].b+c && s[i].b+c>0){ // revoke S is good
// puts("Discard bad B and get B");
sum+=s[i].b+c;
Q2.pop();
Q2.push(pp(-s[i].b,i));
}
} else{ // S==0
}
}
} else{ // M==0
if(S){
// puts("get B");
sum+=s[i].b;
Q2.push(pp(-s[i].b,i));
S--;
}else{
if(!Q2.empty()){
int c=Q2.top().first;
int v2=Q2.top().second;
if(c+s[i].b > 0){ // revoke is good
// puts("Discard bad B and get new B");
sum+=c+s[i].b;
Q2.pop();
Q2.push(pp(-s[i].b,i));
}else{ // revoke isn't good
}
} else{ //S==0
assert(sum==0);
}
}
}
}
// printf("%d : %lld\n",i,sum);
}
printf("%lld\n",sum);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2776 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2776 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2776 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
2776 KB |
Output isn't correct |
| 5 |
Incorrect |
0 ms |
2776 KB |
Output isn't correct |
| 6 |
Incorrect |
0 ms |
2776 KB |
Output isn't correct |
| 7 |
Incorrect |
0 ms |
2776 KB |
Output isn't correct |
| 8 |
Correct |
0 ms |
2908 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
2776 KB |
Output isn't correct |
| 10 |
Incorrect |
0 ms |
2776 KB |
Output isn't correct |
| 11 |
Incorrect |
0 ms |
2912 KB |
Output isn't correct |
| 12 |
Incorrect |
3 ms |
2908 KB |
Output isn't correct |
| 13 |
Incorrect |
0 ms |
3548 KB |
Output isn't correct |
| 14 |
Incorrect |
17 ms |
3808 KB |
Output isn't correct |
| 15 |
Incorrect |
23 ms |
3548 KB |
Output isn't correct |
| 16 |
Incorrect |
18 ms |
3164 KB |
Output isn't correct |
| 17 |
Incorrect |
40 ms |
4316 KB |
Output isn't correct |
| 18 |
Incorrect |
30 ms |
3548 KB |
Output isn't correct |
| 19 |
Incorrect |
30 ms |
5852 KB |
Output isn't correct |
| 20 |
Incorrect |
39 ms |
5852 KB |
Output isn't correct |
