Submission #472011

#	Time	Username	Problem	Language	Result	Execution time	Memory
472011		prvocislo	Cake 3 (JOI19_cake3)	C++17	0 / 100	1 ms	332 KiB

cake3

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
typedef long long ll;
using namespace std;

const int maxn = 1 << 18; 
const ll inf = 1e18;
int cnt[maxn * 2]; 
ll sum[maxn * 2];
void update(int val, int vr)
{
	vr += maxn, cnt[vr] = (val ? 1 : 0), sum[vr] = val;
	for (vr = vr >> 1; vr > 0; vr >>= 1) cnt[vr] = cnt[vr << 1] + cnt[vr << 1 | 1], sum[vr] = sum[vr << 1] + sum[vr << 1 | 1];
}
int n, m, L = 0, R = -1;
struct cake { ll v, c; } c[maxn];
bool cmp(const cake& a, const cake& b) { return a.c < b.c; }
pair<ll, int> v2[maxn];
int ord[maxn];
ll mbest()
{
	ll val = 0; int left = m;
	for (int vr = 1; vr < maxn;)
		if (cnt[vr << 1] <= left)
		{
			left -= cnt[vr << 1];
			val += sum[vr << 1];
			vr = vr << 1 | 1;
		}
		else vr = vr << 1;
	return val;
}
void fix(int l, int r)
{
	while (R < r) R++, update(c[R].v, ord[R]);
	while (L > l) L--, update(c[L].v, ord[L]);
	while (R > r) update(0, ord[R]), R--;
	while (L < l) update(0, ord[L]), L++;
	/*ll a = 0;
	for (int i = L; i <= R; i++) a += c[i].v;
	cout << L << " " << R << " " << sum[1] << " " << a << "\n";*/
}
ll ans = -inf;
void dc(int l1, int l2, int r1, int r2)
{
	if (l2 < l1) return;
	int mid = (l1 + l2) >> 1;
	pair<ll, int> p(-inf, -1);
	for (int i = max(mid + m - 1, r1); i <= r2; i++)
	{
		fix(mid, i);
		pair<ll, int> p2(mbest() - 2ll * (c[i].c - c[mid].c), i);
		p = max(p, p2);
	}
	ans = max(ans, p.first);
	dc(l1, mid - 1, r1, p.second);
	dc(mid + 1, l2, p.second, r2);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> c[i].v >> c[i].c, v2[i] = { c[i].v, i };
	sort(c, c + n, cmp);
	sort(v2, v2 + n, greater<pair<int, int> > ());
	for (int i = 0; i < n; i++) 
		ord[v2[i].second] = i;
	dc(0, n - m, m - 1, n - 1);
	cout << ans << "\n";
	return 0;
}

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