| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 18149 | comet | Schools (IZhO13_school) | C++98 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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);
}