Submission #250061

#	Time	Username	Problem	Language	Result	Execution time	Memory
250061		dtc03012	Schools (IZhO13_school)	C++17	30 / 100	161 ms	14816 KiB

school

#include <bits/stdc++.h>
using namespace std;
typedef long long int lld;
typedef pair<int,int> pi;
typedef pair<lld,lld> pl;
typedef vector<int> vit;
typedef vector<vit> vitt;
typedef vector<lld> vlt;
typedef vector<vlt> vltt;
typedef vector<pi> vpit;
typedef vector<vpit> vpitt;
typedef long double ld;
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()
#define mk(a,b) make_pair(a,b)
bool isrange(int y,int x,int n,int m){
	 if(0<=y&&y<n&&0<=x&&x<m) return true;
	 return false;
}
int dy[4] = {1,0,-1,0},dx[4]={0,1,0,-1},ddy[8] = {1,0,-1,0,1,1,-1,-1},ddx[8] = {0,1,0,-1,1,-1,1,-1};
pl arr[333333];
bool tmr(pl a,pl b){
	return a.x > b.x;
}
bool tmr2(pl a,pl b){
	return a.y > b.y;
}
priority_queue<pair<lld,int> > q1,q2,q3;
int main(void){
	int n,f,s;
	scanf("%d%d%d",&n,&f,&s);
	for(int e=0;e<n;e++) scanf("%lld%lld",&arr[e].x,&arr[e].y);
	if(f==0){
		sort(arr,arr+n,tmr2);
		lld ans = 0;
		for(int e=0;e<s;e++) ans += arr[e].y;
		return !printf("%lld",ans);
	}else if(s==0){
		sort(arr,arr+n,tmr);
		lld ans = 0;
		for(int e=0;e<f;e++) ans += arr[e].x;
		return !printf("%lld",ans);
	}
	sort(arr,arr+n,tmr);
	lld ans = 0;
	for(int e=0;e<f;e++) {
		ans += arr[e].x;
		q1.push(mk(-arr[e].x+arr[e].y,e));
	}
	for(int e=f;e<f+s;e++){
		lld tt = -q1.top().x;
		int wh = q1.top().y;
		if(arr[e].x-arr[e].y>=tt){
			ans += (arr[e].x-tt);
			q1.pop();
			q2.push(mk(-arr[wh].y,wh));
			q1.push(mk(-arr[e].x+arr[e].y,e));
		}else{
			ans += (arr[e].y);
			q2.push(mk(-arr[e].y,e));
		}
	}
	while(!q1.empty()){
		int wh = q1.top().y;
		q1.pop();
		q3.push(mk(-arr[wh].x,wh)); 
	}
	for(int e=(f+s);e<n;e++){
		lld tt1 = -q3.top().x;
		int wh1 = q3.top().y;
		lld tt2 = -q2.top().x;
		int wh2 = q2.top().y;
		if(arr[e].x-tt1>=arr[e].y-tt2){
			if(arr[e].x-tt1<=0) continue;
			else{
				ans += (arr[e].x-tt1);
				q3.pop();
				q3.push(mk(-arr[e].x,e));
				if(arr[wh1].y>tt2){
					ans += (arr[wh1].y-tt2);
					q2.pop();
					q2.push(mk(-arr[wh1].y,wh1));
				}
			}
		}else{
			if(arr[e].y-tt2<=0) continue;
			else{
				ans += (arr[e].y-tt2);
				q2.pop();
				q2.push(mk(-arr[e].y,e));
				if(arr[wh2].x>tt1){
					ans += (arr[wh2].x - tt1);
					q3.pop();
					q3.push(mk(-arr[wh2].x,wh2));
				}
			}
		}
	}
	printf("%lld",ans);
	return 0;
}

Compilation message (stderr)

school.cpp: In function 'int main()':
school.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&f,&s);
  ~~~~~^~~~~~~~~~~~~~~~~~~
school.cpp:34:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int e=0;e<n;e++) scanf("%lld%lld",&arr[e].x,&arr[e].y);
                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 100