Submission #447697

#	Time	Username	Problem	Language	Result	Execution time	Memory
447697		dutch	Cake 3 (JOI19_cake3)	C++17	100 / 100	553 ms	15048 KiB

cake3

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

const int LIM = 2e5, INF = 1e18;

int n, m, L, R, fVal[LIM+1], fCnt[LIM+1], pos[LIM], ans = -INF;
array<int, 2> a[LIM], b[LIM];

void add(int i, int j){
	int v = a[i][1] * j; i = pos[i];
	for(; i<=n; i+=i&-i){
		fCnt[i] += j;
		fVal[i] += v;
	}
}

int get(int l, int r){
	assert(r-l >= m-2);
	while(R < r) add(R++, 1);
	while(L > l) add(--L, 1);
	while(R > r) add(--R,-1);
	while(L < l) add(L++,-1);

	int v = m - 2, i = 0, s = 0;
	for(int j=1<<19; j/=2; ){
		if(i+j <= n && fCnt[i+j] <= v){
			i += j;
			s += fVal[i];
			v -= fCnt[i];
		}
	}
	return s;
}

void find(int lx, int rx, int l, int r){
	if(rx - lx < 1) return;
	int mx = (lx + rx) / 2;
	array<int, 2> res = {-INF, -1};
	for(int i=l; i<min(r, mx-m+2); ++i){
		res = max(res, {get(i+1, mx) + a[i][1] + a[mx][1] - 2 * (a[mx][0] - a[i][0]), i});
	}
	ans = max(ans, res[0]);
	find(lx, mx, l, res[1] + 1);
	find(mx+1, rx, res[1], r);
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	for(int i=0; i<n; ++i){
		cin >> a[i][1] >> a[i][0];
	}
	sort(a, a+n);
	for(int i=0; i<n; ++i){
		b[i][0] = a[i][1];
		b[i][1] = i;
	}
	sort(b, b+n);
	for(int i=0; i<n; ++i){
		pos[b[i][1]] = n - i;
	}
	find(m-1, n, 0, n-m+1);
	cout << ans;
}

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