Submission #1176157

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176157		KK_1729	Cake 3 (JOI19_cake3)	C++20	24 / 100	4096 ms	57456 KiB

cake3

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

// #define int long long
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"

void printVector(vector<int> a){
	for (auto x: a) cout << x << " ";
	cout << endl;
}

int n, m;
vector<pair<int, int>> cakes;
vector<long long> val;
void dnc(int l, int r, int optl, int optr){
	if (l > r) return;

	
	int mid = (l+r)/2;
	if (n-mid < m-1){

		dnc(l, mid-1, optl, optr);
		// dnc(mid+1, r, optl, optr);
		return;
	}
	pair<long long, int> best = {-1e17, mid};
	multiset<int> o; long long u = 0ll;
	for (int j = mid+1; j < mid+m-1; ++j){
		o.insert(cakes[j].second);
		u += cakes[j].second;
	}
	for (int j = mid+m-1; j <= optr; j++){
		long long t = cakes[mid].second+cakes[j].second+u-2*(cakes[j].first-cakes[mid].first);

		best = max(best, {t, j});
		// if (mid == 3) cout << t << endl;
		if (cakes[j].second > *(o.begin())){
			u -= *(o.begin());
			o.erase(o.begin());
			o.insert(cakes[j].second);
			u += cakes[j].second;
		}
	}
	// cout << mid << best.first << best.second << endl;
	val[mid] = best.first;
	int opt = best.second;
	dnc(l, mid-1, optl, opt);

	dnc(mid+1, r, opt, optr);
}
void solve(){
	cin >> n >> m;
	cakes.pb({-1,-1});
	val.resize(n+1, -1e17);
	FOR(i,0,n){

		int v, c; cin >> v >> c;
		cakes.pb({c, v});

	}
	sort(all(cakes));
	dnc(1, n, 1, n);
	long long ans = -1e17;
	// printVector(val);
	FOR(i,1,n+1) ans = max(ans, val[i]);
	cout << ans << endl;

}


int32_t main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);
	int t = 1; // cin >> t;
	while (t--) solve();
}

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