Submission #105853

#	Time	Username	Problem	Language	Result	Execution time	Memory
105853		Pro_ktmr	Cake 3 (JOI19_cake3)	C++14	0 / 100	3 ms	384 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> VC[200000];

int main(){
	cin >> N >> M;
	for(int i=0; i<N; i++){
		cin >> VC[i].first >> VC[i].second;
	}
	sort(VC, VC+N);
	
	//
	
	LL now = 0;
	multiset<pair<int,int>> st;
	for(int i=0; i<M; i++){
		now += VC[N-1-i].first;
		st.insert(MP(VC[N-1-i].second,VC[N-1-i].first));
	}
	auto itr = st.end();
	itr--;
	//now -= 2*(itr->first-st.begin()->first);
	
	//cout << now << endl;
	LL ans = now-2*(itr->first-st.begin()->first);
	LL bef = ans;
	for(int i=N-1-M; i>=0; i--){
		now += VC[i].first;
		st.insert(MP(VC[i].second,VC[i].first));
		LL tmpL,tmpR;

		tmpL = now;
		tmpL -= st.begin()->second;
		auto itr = st.end();
		itr--;
		auto it = st.begin();
		it++;
		tmpL -= 2*(itr->first-it->first);
		
		tmpR = now;
		itr = st.end();
		itr--;
		tmpR -= itr->second;
		itr--;
		it = st.begin();
		tmpR -= 2*(itr->first-it->first);
		
		if(bef > tmpL && bef > tmpR){
			now -= VC[i].first;
			st.erase(MP(VC[i].second,VC[i].first));
		}
		if(tmpL > tmpR){
			now -= st.begin()->second;
			st.erase(st.begin());
		}
		else{
			it = st.end();
			it--;
			now -= it->second;
			st.erase(it);
		}
		itr = st.end(); itr--;
		ans = max(ans, now-2*(itr->first-st.begin()->first));
		bef = now-2*(itr->first-st.begin()->first);
		//cout << tmpL << " " << tmpR << endl;
	}
	
	cout << ans << endl;
	
	return 0;
}

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