Submission #250299

#TimeUsernameProblemLanguageResultExecution timeMemory
250299dtc03012학교 설립 (IZhO13_school)C++17
15 / 100
182 ms21552 KiB
#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};
vector<pl> f,s;
pl arr[333333];
lld ans;
int vis[333333];
priority_queue<lld> q;
bool tmr(pl a,pl b){
	return a.x > b.x;
}
priority_queue<pair<lld,int> > q1,q2;
int main(void){
	int n,a,b;
	scanf("%d%d%d",&n,&a,&b);
	for(int e=0;e<n;e++){
		lld a,b;
		scanf("%lld%lld",&a,&b);
		arr[e] = mk(a,b);
		f.push_back(mk(a,e));
		s.push_back(mk(b,e));
	}
	sort(all(f),tmr);
	sort(all(s),tmr);
	lld ans = 0;
	for(int e=0;e<a;e++){
		int wh = f[e].y;
		q1.push(mk(-(arr[wh].x-arr[wh].y),wh));
		ans += arr[wh].x;
		vis[wh] = 1;
	}
	for(int e=0,st=0;e<n&&st<b;e++){
		int wh = s[e].y;
		if(vis[wh]) continue;
		st++;
		vis[wh] = 1;
		ans += arr[wh].y;
		q2.push(mk(-(arr[wh].x-arr[wh].y),wh));
	}
	for(int e=0;e<n;e++) if(vis[e]==0) q.push(arr[e].y);
	while(!q1.empty()){
		lld tt1 = -q1.top().x;
		int wh1 = q1.top().y;
		while(!q2.empty()){
			lld tt2 = -q2.top().x;
			int wh2 = q2.top().y;
			q2.pop();
			if(tt1<tt2){
				ans -= (arr[wh1].x+arr[wh2].y);
				ans += (arr[wh2].x);
				if(sz(q)==0) ans += arr[wh1].y;
				else{
					lld tt3 = q.top();
					if(arr[wh1].y>tt3) ans += arr[wh1].y;
					else{
						ans += tt3;
						q.pop();
						q.push(arr[wh1].y);
					}
				}
				q1.pop();
				break;
			}
		}
		if(sz(q2)==0) break; 
	}
	printf("%lld",ans);
	return 0;
}

Compilation message (stderr)

school.cpp: In function 'int main()':
school.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&a,&b);
  ~~~~~^~~~~~~~~~~~~~~~~~~
school.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&a,&b);
   ~~~~~^~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...