oj.uz

Submission #105853

# Submission time Handle Problem Language Result Execution time Memory
105853 2019-04-15T10:40:25 Z Pro_ktmr Cake 3 (JOI19_cake3) C++14
0 / 100
 3 ms 384 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 3 ms 300 KB Output is correct
6 Correct 3 ms 256 KB Output is correct
7 Incorrect 2 ms 384 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 3 ms 300 KB Output is correct
6 Correct 3 ms 256 KB Output is correct
7 Incorrect 2 ms 384 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 76.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 3 ms 300 KB Output is correct
6 Correct 3 ms 256 KB Output is correct
7 Incorrect 2 ms 384 KB Output isn't correct
8 Halted 0 ms 0 KB -