Submission #18150

# Submission time Handle Problem Language Result Execution time Memory
18150 2016-01-25T00:39:26 Z comet Schools (IZhO13_school) C++14
20 / 100
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