제출 #18151

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
18151		comet	학교 설립 (IZhO13_school)	C++14	20 / 100	35 ms	5852 KiB

school

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

}

• Subtask 1: 20 / 100