Submission #96220

#	Time	Username	Problem	Language	Result	Execution time	Memory
96220		Retro3014	Schools (IZhO13_school)	C++17	45 / 100	125 ms	8672 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<int> pq;
struct S2{
	S2 (int x, int y) : x(x), y(y) {}
	int x, y;
	bool operator <(const S2 &a)const{
		return a.x<x;
	}
};
priority_queue<S2> pq2;
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(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({v[i].y, i});	sum2+=v[i].y;
			chk[i] = true;
		}
		else{
			if(pq2.top().x<v[i].y){
				sum2-=pq2.top().x; sum2+=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 += v[M+i].x;
		pq.push(v[M+i].y-v[M+i].x);
		//cout<<'&'<<pq.top()<<endl;
		sum += pq.top(); pq.pop();
		if(chk[M+i]){
			sum2 -= v[M+i].y;
		}else{
			//cout<<'*'<<pq2.top().x<<endl;
			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:53:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(pq2.size()<S){
      ~~~~~~~~~~^~
school.cpp:36: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:39: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: 45 / 100