Submission #838738

#	Time	Username	Problem	Language	Result	Execution time	Memory
838738		beaboss	Cake 3 (JOI19_cake3)	C++14	5 / 100	4054 ms	568 KiB

cake3

// Source: https://oj.uz/problem/view/JOI19_cake3
// 

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<ll, ll> pii;
typedef vector<pii> vpii;

typedef vector<ll> vi;

#define FOR(i, a, b) for (ll i = (a); i<b; i++)

const ll N = 2e5 + 10;

ll n, m;
pii inp[N];

ll ans = -1e18;

void solve(ll ia, ll ib, ll ja, ll jb) { // solves range [ia, ib) assuming the previous DP can be from [ja, jb]
	if (ia == ib) return;
	

	ll i = (ia + ib) / 2;
	
	if (i-m+1 < ja) {
		solve(i + 1, ib, ja, jb);
		return; // to few numbers
	}

	ll arg_j = 0;

	ll sum = 0;
	ll opt = 0;

	multiset<ll> vals;

	for (ll j = i; j > i-m; j--) {
		vals.insert(inp[j].s);
		sum+=inp[j].s;
	}

	opt = sum - 2ll * (inp[i].f - inp[i-m+1].f);

	for (ll j = i-m; j >= ja; j--) {
		
		sum += inp[j].s;
		vals.insert(inp[j].s);
		sum -= *vals.begin();
		vals.erase(vals.begin());

		ll v = sum - 2ll * (inp[i].f - inp[j].f);

		if (v > opt) {
			arg_j = j;
			opt=v;
		}
	}

	// cout << i << ' ' << opt << endl;

	ans = max(ans, opt);

	solve(ia, i, 0, n);
	solve(i + 1, ib, 0, n);
	solve(ia, i, ja, arg_j);
	solve(i + 1, ib, arg_j, jb);

}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> m;

	FOR(i, 0, n) cin >> inp[i].s >> inp[i].f;

	sort(inp, inp + n);

	// FOR(i, 0, n) cout << inp[i].s << ' ' << inp[i].f << endl;

	solve(0, n, 0, n);
	cout << ans << endl;

}

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