제출 #362674

#제출 시각아이디문제언어결과실행 시간메모리
362674RyoPhamCake 3 (JOI19_cake3)C++14
0 / 100
1 ms384 KiB
#define taskname "test" #include <bits/stdc++.h> using namespace std; #define sz(x) (int)x.size() #define fi first #define se second typedef long long lli; typedef pair<int, int> pii; const int maxn = 2e5 + 5; const lli inf = 1e18; int n, m; pii cakes[maxn]; vector<int> vals; lli f[maxn]; struct segment_tree { lli total[maxn * 4]; int cnt[maxn * 4]; void update(int x, int l, int r, int p, int k) { if(l == r) { total[x] += vals[l - 1] * k; cnt[x] += k; return; } int mid = (l + r) / 2; if(p <= mid) update(x * 2, l, mid, p, k); else update(x * 2 + 1, mid + 1, r, p, k); total[x] = total[x * 2] + total[x * 2 + 1]; cnt[x] = cnt[x * 2] + cnt[x * 2 + 1]; } lli get(int x, int l, int r, int k) { if(l == r) return vals[l] * 1LL * min(k, cnt[x]); int mid = (l + r) / 2; if(cnt[x * 2 + 1] <= k) return total[x * 2 + 1] + get(x * 2, l, mid, k - cnt[x * 2 + 1]); else return get(x * 2 + 1, mid + 1, r, k); } } tree; void read_input() { cin >> n >> m; for(int i = 1; i <= n; ++i) cin >> cakes[i].fi >> cakes[i].se; } void init() { sort(cakes + 1, cakes + n + 1, [](pii p, pii q) { return p.se < q.se; }); for(int i = 1; i <= n; ++i) vals.push_back(cakes[i].fi); sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); for(int i = 1; i <= n; ++i) cakes[i].fi = lower_bound(vals.begin(), vals.end(), cakes[i].fi) - vals.begin() + 1; } lli query(int l, int r) { static int curl = 1, curr = 0; while(curr < r) { ++curr; tree.update(1, 1, sz(vals), cakes[curr].fi, 1); } while(curr > r) { tree.update(1, 1, sz(vals), cakes[curr].fi, -1); --curr; } while(curl > l) { --curl; tree.update(1, 1, sz(vals), cakes[curl].fi, 1); } while(curl < l) { tree.update(1, 1, sz(vals), cakes[curl].fi, -1); ++curl; } return tree.get(1, 1, sz(vals), m - 2); } void dnc(int l, int r, int optl, int optr) { if(l > r) return; int mid = (l + r) / 2; lli best = -inf; int opt = 0; for(int i = max(mid + m - 1, optl); i <= optr; ++i) { lli k = query(mid + 1, i - 1) + vals[cakes[mid].fi - 1] + vals[cakes[i].fi - 1] - 2LL * (cakes[i].se - cakes[mid].se); if(k > best) { best = k; opt = i; } } f[mid] = best; dnc(l, mid - 1, optl, opt); dnc(mid + 1, r, opt, optr); } void solve() { dnc(1, n - m + 1, 1, n); lli ans = -inf; for(int i = 1; i <= n - m + 1; ++i) ans = max(ans, f[i]); cout << ans << '\n'; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); read_input(); init(); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...