Submission #900021

#	Time	Username	Problem	Language	Result	Execution time	Memory
900021		DEQK	Cake 3 (JOI19_cake3)	C++17	100 / 100	3075 ms	16100 KiB

cake3

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define sz(a) ((int) a.size())
#define F first
#define S second
const int N = 3e5 + 15;
int n, K;
pair<int, int> a[N];
ll ans = -1e18;
int L = 1, R = 0;
ll cur = 0;
set<pair<int, int>> sm, bg;
void add(int p) {
	if(sz(bg) < K) {
		cur += a[p].S;
		bg.insert({a[p].S, p});
	} else {
		assert(sz(bg) == K);
		if(a[p].S > (*(bg.begin())).F) {
			cur -= (*bg.begin()).F;
			sm.insert(*bg.begin());
			bg.erase(bg.begin());
			bg.insert({a[p].S, p});
			cur += a[p].S;
		} else {
			sm.insert({a[p].S, p});
		}
	}
}
void del(int p) {
	if(bg.count({a[p].S, p})) {
		cur -= a[p].S;
		bg.erase({a[p].S, p});
		if(sz(sm)) {
			auto it = sm.end();
			it--;
			cur += (*it).F;
			bg.insert(*it);
			sm.erase(it);
		}
	} else {
		assert(sm.find({a[p].S, p}) != sm.end());
		sm.erase(sm.find({a[p].S, p}));
	}
}
void dnc(int l, int r, int tl, int tr) {
	if(l > r) {
		return;
	}
	int m = (l + r) / 2;
	int pt = tl;
	ll mx = -1e18;
	//cout << l << ' ' << r << ' ' << tl << ' ' << tr << '\n';
	for(int k = tl; k <= min(tr, m); k++) {
		while(R < m) {
			add(++R);
		}
		while(L > k) {
			add(--L);
		}
		while(R > m) {
			del(R--);
		}
		while(L < k) {
			del(L++);
		}
		if(sz(bg) == K && mx < cur - 2 * (a[m].F - a[k].F)) {
			mx = cur - 2 * (a[m].F - a[k].F);
			pt = k;
		}
	}
	ans = max(ans, mx);
	dnc(l, m - 1, tl, pt);
	dnc(m + 1, r, pt, tr);
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> K;
	for(int i = 1; i <= n; i++) {
		cin >> a[i].S;
		cin >> a[i].F;
	}
	sort(a + 1, a + n + 1);
	dnc(1, n, 1, n);
	cout << ans << '\n';
}

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