Submission #120911

#	Time	Username	Problem	Language	Result	Execution time	Memory
120911		youngyojun	Cake 3 (JOI19_cake3)	C++11	100 / 100	1173 ms	15180 KiB

cake3

#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define upmax(a,b) (a)=max((a),(b))
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;

const bool debug = 0;

const int MAXN = 200055;

struct SEG {
	ll ds[MAXN*4];
	int dc[MAXN*4];

	void push(int i, int s, int e, int x, ll r) {
		ds[i] += r; dc[i]++;
		if(s == e) return;
		int m = (s+e) >> 1;
		if(x <= m) push(i<<1, s, m, x, r);
		else push(i<<1|1, m+1, e, x, r);
	}
	void pop(int i, int s, int e, int x, ll r) {
		ds[i] -= r; dc[i]--;
		if(s == e) return;
		int m = (s+e) >> 1;
		if(x <= m) pop(i<<1, s, m, x, r);
		else pop(i<<1|1, m+1, e, x, r);
	}
	ll get(int i, int s, int e, int c) {
		if(!c) return 0;
		if(dc[i] == c) return ds[i];
		int m = (s+e) >> 1;
		if(c <= dc[i<<1]) return get(i<<1, s, m, c);
		else return get(i<<1, s, m, dc[i<<1]) + get(i<<1|1, m+1, e, c - dc[i<<1]);
	}
} seg;

int PQs, PQe;

ll A[MAXN], B[MAXN];
int AO[MAXN], ARO[MAXN];

ll Ans = -INFLL;
int N, M;

void f(int s, int e) {
	for(; s < PQs;) {
		PQs--;
		seg.push(1, 1, N, ARO[PQs], A[PQs]);
	}
	for(; PQe < e;) {
		PQe++;
		seg.push(1, 1, N, ARO[PQe], A[PQe]);
	}
	for(; PQs < s;) {
		seg.pop(1, 1, N, ARO[PQs], A[PQs]);
		PQs++;
	}
	for(; e < PQe;) {
		seg.pop(1, 1, N, ARO[PQe], A[PQe]);
		PQe--;
	}
}

void f(int s, int e, int p, int q) {
	if(s > e || p > q) return;
	int m = (s+e) >> 1;
	ll hc = -INFLL; int hi = -1;
	for(int i = max(m+M+1, p); i <= q; i++) {
		f(m+1, i-1);
		ll ret = seg.get(1, 1, N, M) + A[m] + B[m] + A[i] - B[i];
		if(ret <= hc) continue;
		hc = ret; hi = i;
	}
	if(debug) {
		printf("F %d %d %d %d / %d %lld %d\n", s, e, p, q, m, hc, hi);
	}
	upmax(Ans, hc);
	f(s, m-1, p, hi);
	f(m+1, e, hi, q);
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N >> M; M -= 2;
	{
		vector<pll> V;
		for(int i = 0, a, b; i < N; i++) {
			cin >> a >> b;
			V.eb(b << 1, a);
		}
		sorv(V);
		for(int i = 1; i <= N; i++)
			tie(B[i], A[i]) = V[i-1];
	}
	iota(AO, AO+N+1, 0);
	sort(AO+1, AO+N+1, [&](int a, int b) {
		return A[a] > A[b];
	});
	for(int i = 1; i <= N; i++) ARO[AO[i]] = i;

	PQs = PQe = 1;
	seg.push(1, 1, N, ARO[1], A[1]);

	if(debug) {
		for(int i = 1; i <= N; i++)
			printf("%d ; %d %lld %lld\n", i, ARO[i], A[i], B[i]);
	}

	f(1, N-M-1, 1, N);

	cout << Ans << endl;
	return 0;
}

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