Submission #249460

#	Time	Username	Problem	Language	Result	Execution time	Memory
249460		lyc	Cake 3 (JOI19_cake3)	C++14	24 / 100	4059 ms	4840 KiB

cake3

#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

const int mxN = 2e5+5;

int N, M;
struct Cake { int V, C; } cake[mxN];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> N >> M;
	FOR(i,1,N){
		int V, C; cin >> V >> C;
		cake[i] = {V,C};
	}
	
	sort(cake+1,cake+1+N,[](Cake a, Cake b){ return a.C != b.C ? a.C < b.C : a.V < b.V; });
	long long ans = -1e18;
	FOR(l,1,N){
		multiset<int> ms;
		long long cur = 0;
		FOR(r,l,N){
			if (SZ(ms) < M) ms.insert(cake[r].V), cur += cake[r].V;
			else if (cake[r].V > *ms.begin()) {
				cur -= *ms.begin();
				ms.erase(ms.begin());
				ms.insert(cake[r].V);
				cur += cake[r].V;
			}
			
			if (SZ(ms) == M) {
				ans = max(ans,cur-2*(cake[r].C-cake[l].C));
			}
		}
	}
	cout << ans << '\n';
}

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