제출 #838742

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
838742		beaboss	Cake 3 (JOI19_cake3)	C++14	24 / 100	4059 ms	54132 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
	// }
	assert(i - m + 1 >= ja);

	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(max(arg_j + m - 1, 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(m-1, n, 0, n);
	cout << ans << endl;

}

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