| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 973010 | Double_Slash | Cake 3 (JOI19_cake3) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define debug(x) [&](){ auto _x = x; cerr << __LINE__ << ": " << #x << " = " << _x << endl; }()
using namespace std;
typedef long long ll;
#define all(x) x.begin(), x.end()
const int INF = 1e9;
const ll LLINF = 1e18;
int n, m, v[200001], c[200001];
ll ans;
struct Node {
int freq = 0;
ll sum = 0;
Node *lc = nullptr, *rc = nullptr;
Node *pull(Node *ln, Node *rn) {
return new Node{ln->freq + rn->freq, ln->sum + rn->sum, ln, rn};
}
Node *update(int i, int v, int l, int r) {
if (l == r) return new Node{freq + 1, sum + v};
int m = (l + r) >> 1;
if (i <= m) return pull(lc->update(i, l, m), rc);
else return pull(lc, rc->update(i, m + 1, r));
}
} *st[200001];
ll walk(Node *ln, Node *rn, int k, int l, int r) {
if (l == r) return (ll) k * rn->sum / rn->freq;
int rfreq = rn->rc ? rn->rc->freq - (ln and ln->rc ? ln->rc->freq : 0) : 0;
int m = (l + r) >> 1;
if (k <= rfreq) return walk(ln ? ln->rc : nullptr, rn->rc, k, m + 1, r);
else return walk(ln ? ln->lc : nullptr, rn->lc, k - rfreq, l, m) + (rn->rc ? rn->rc->sum - (ln and ln->rc ? ln->rc->sum : 0) : 0);
}
ll calc(int l, int r) {
if (r - l + 1 < m) return -LLINF;
return walk(st[l - 1], st[r], m, 1, INF) - (c[r] - c[l]) * 2;
}
void dnc(int l, int r, int optl, int optr) {
if (l > r) return;
int mid = (l + r) >> 1;
pair<ll, int> mx{-LLINF, 0};
for (int k = max(optl, mid + m - 1); k <= optr; ++k) {
mx = max(mx, {calc(mid, k), k});
}
ans = max(ans, mx.first);
dnc(l, mid - 1, optl, mx.second);
dnc(mid + 1, r, mx.second, optr);
}
int main() {
cin >> n >> m;
vector<pair<int, int>> raw(n);
map<int, int> cc;
for (auto &[b, a]: raw) {
cin >> a >> b;
cc[a] = 0;
}
int j = 1;
for (auto &[k, v]: cc) v = j++;
sort(all(raw));
st[0] = new Node{};
st[0]->lc = st[0]->rc = st[0];
for (int i = 1; i <= n; ++i) {
tie(c[i], v[i]) = raw[i - 1];
st[i] = st[i - 1]->update(cc[v[i]], v[i], 1, n);
}
ans = -LLINF;
dnc(1, n - m + 1, m, n);
cout << ans << endl;
}