답안 #18151

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
18151 2016-01-25T00:40:21 Z comet 학교 설립 (IZhO13_school) C++14
20 / 100
35 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

				ll 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

						ll 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()){

						ll 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);

}
# 결과 실행 시간 메모리 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 2 ms 2912 KB Output isn't correct
12 Incorrect 0 ms 2908 KB Output isn't correct
13 Incorrect 12 ms 3548 KB Output isn't correct
14 Incorrect 33 ms 3808 KB Output isn't correct
15 Incorrect 35 ms 3548 KB Output isn't correct
16 Incorrect 0 ms 3164 KB Output isn't correct
17 Incorrect 35 ms 4316 KB Output isn't correct
18 Incorrect 28 ms 3548 KB Output isn't correct
19 Incorrect 34 ms 5852 KB Output isn't correct
20 Incorrect 33 ms 5852 KB Output isn't correct