Submission #96222

#	Time	Username	Problem	Language	Result	Execution time	Memory
96222		Retro3014	Schools (IZhO13_school)	C++17	80 / 100	142 ms	11108 KiB

school

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <queue>

using namespace std;
typedef long long ll;
#define MAX_N 300000

int N, M, S;
struct ST{
	ST (int x, int y) : x(x), y(y) {}
	int x, y;
	bool operator <(const ST &a)const{
		if(x==a.x)	return y<a.y;
		return x>a.x;
	}
};
vector<ST> v;
priority_queue<ll> pq;
struct S2{
	S2 (ll x, int y) : x(x), y(y) {}
	ll x;
	int y;
	bool operator <(const S2 &a)const{
		return a.x<x;
	}
};
priority_queue<S2> pq2, pq3;
ll ans;


bool chk[MAX_N+1];

int main(){
	scanf("%d%d%d", &N, &M, &S);
	for(int i=0; i<N; i++){
		int a, b;
		scanf("%d%d", &a, &b);
		v.push_back({a, b});
	}sort(v.begin(), v.end());
	//for(int i=0; i<N; i++){
	//	cout<<v[i].x<<' '<<v[i].y<<endl;
	//}cout<<endl;
	ll sum = 0;
	for(int i=0; i<M; i++){
		sum+=v[i].x;
		pq.push((ll)(v[i].y-v[i].x));
	}
	ll sum2 = 0;
	for(int i=M; i<N; i++){
		if(S==0)	continue;
		if(pq2.size()<S){
			pq2.push({(ll)v[i].y, i});	sum2+=(ll)v[i].y;
			chk[i] = true;
		}
		else{
			if(pq2.top().x<v[i].y){
				sum2-=pq2.top().x; sum2+=(ll)v[i].y;
				chk[pq2.top().y] = false; chk[i] = true;
				pq2.pop(); pq2.push({v[i].y, i});
			}
		}
	}
	for(int i=0; i<=S; i++){
		ans = max(ans, sum+sum2);
		if(i==S)	continue;
		sum += (ll)v[M+i].x;
		pq.push((ll)(v[M+i].y-v[M+i].x));
		//cout<<'&'<<pq.top()<<endl;
		sum += pq.top(); pq.pop();
		if(chk[M+i]){
			sum2 -= (ll)v[M+i].y;
			pq3.push({(ll)v[M+i].y, M+i});
		}else{
			//cout<<'*'<<pq2.top().x<<endl;
			while(!pq2.empty() && !pq3.empty() && pq2.top().x==pq3.top().x && pq2.top().y==pq3.top().y)	{
				pq2.pop(); pq3.pop();
			}
			sum2 -= pq2.top().x;
			chk[pq2.top().y] = false;
			pq2.pop();
		}
	}
	printf("%lld", ans);
	return 0;
}

Compilation message (stderr)

school.cpp: In function 'int main()':
school.cpp:54:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(pq2.size()<S){
      ~~~~~~~~~~^~
school.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &M, &S);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
school.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 80 / 100