Submission #706240

#	Time	Username	Problem	Language	Result	Execution time	Memory
706240		alvingogo	Cake 3 (JOI19_cake3)	C++14	24 / 100	4027 ms	6072 KiB

cake3

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

/* 
Cake: idk

LCBorz

*/
int main(){
	AquA;
	int n,m;
	cin >> n >> m;
	vector<pair<int,int> > v(n);
	for(int i=0;i<n;i++){
		cin >> v[i].fs >> v[i].sc;
	}
	sort(v.begin(),v.end(),[&](pair<int,int> a,pair<int,int> b){return a.sc<b.sc;});
	long long ans=-1e18;
	for(int i=m-1;i<n;i++){
		p_q<int,vector<int>,greater<int> > pq;
		long long sum=0;
		int cnt=0;
		for(int j=i;j>=0;j--){
			cnt++;
			sum+=v[j].fs;
			pq.push(v[j].fs);
			if(cnt>m){
				cnt--;
				sum-=pq.top();
				pq.pop();
			}
			if(cnt>=m){
				ans=max(ans,sum-2*(v[i].sc-v[j].sc));
			}
		}
	}
	cout << ans << "\n";
	return 0;
}

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