Submission #105850

#	Time	Username	Problem	Language	Result	Execution time	Memory
105850		Pro_ktmr	Cake 3 (JOI19_cake3)	C++14	0 / 100	4075 ms	256 KiB

cake3

#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define MP make_pair
#define PB push_back

int N,M;
pair<LL,LL> CV[200000];
pair<LL,int> V[200000];

int main(){
	cin >> N >> M;
	if(N > 2000) return -1;
	for(int i=0; i<N; i++){
		cin >> CV[i].second >> CV[i].first;
	}
	sort(CV, CV+N);
	for(int i=0; i<N; i++){
		V[i] = MP(CV[i].second,i);
	}
	sort(V, V+N);
	
	//
	
	LL now = -(CV[N-1].first-CV[0].first)*2;
	multiset<int> use;
	for(int i=0; i<M; i++){
		now += V[N-1-i].first;
		use.insert(V[N-1-i].second);
	}
	priority_queue<pair<LL,int>> que;
	for(int i=M; i<N; i++){
		que.push(V[N-1-i]);
	}
	
	LL maximum = now;
	LL r = N;
	
	for(int i=N-1; i>=M; i--){
		now += 2*(CV[i].first-CV[i-1].second);
		if(use.count(i) == 1){
			use.erase(i);
			now -= CV[i].second;
			while(que.top().second >= i) que.pop();
			now += que.top().first;
			use.insert(que.top().second);
			que.pop();
		}
		if(maximum < now){
			maximum = now;
			r = i;
		}
	}
	
	//
	
	now = -(CV[N-1].first-CV[0].first)*2;
	use.clear();
	for(int i=0; i<M; i++){
		now += V[N-1-i].first;
		use.insert(V[N-1-i].second);
	}
	while(!que.empty()) que.pop();
	for(int i=M; i<N; i++){
		que.push(V[N-1-i]);
	}
	
	maximum = now;
	LL l = -1;
	
	for(int i=0; i<N-M; i++){
		now += 2*(CV[i+1].first-CV[i].second);
		if(use.count(i) == 1){
			use.erase(i);
			now -= CV[i].second;
			while(que.top().second >= i) que.pop();
			now += que.top().first;
			use.insert(que.top().second);
			que.pop();
		}
		if(maximum < now){
			maximum = now;
			l = i;
		}
	}
	
	//
	
	vector<LL> v;
	LL ans = -(CV[r-1].first-CV[l+1].first)*2;
	for(int i=l+1; i<=r-1; i++){
		v.PB(CV[i].second);
	}
	sort(v.begin(), v.end());
	for(int i=0; i<M; i++) ans += v[v.size()-1-i];
	
	cout << l << " " << r << endl;
	cout << ans << endl;
	
	return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 19
• Subtask 3: 0 / 76