Submission #263354

#TimeUsernameProblemLanguageResultExecution timeMemory
263354keko37Cake 3 (JOI19_cake3)C++14
100 / 100
1472 ms12008 KiB
#include<bits/stdc++.h> using namespace std; typedef long long llint; typedef pair <int, int> pi; const int MAXN = 200005; const llint INF = 1000000000000000000LL; llint n, m, sum, sol = -INF, br; pi p[MAXN]; int pos[MAXN], fen[MAXN]; vector <pi> v, saz; bool cmp (pi a, pi b) { return a.second < b.second; } void fen_ubaci (int x, int k) { for (; x < MAXN; x += x&-x) fen[x] += k; } int get () { int res = 0; for (int i = 17; i >= 0; i--) { if (res + (1 << i) < MAXN && fen[res + (1 << i)] == 0) res += (1 << i); } return res + 1; } void ubaci (int ind) { //cout << "ubaci " << ind << endl; sum += p[ind].first; br++; fen_ubaci(pos[ind], 1); if (br > m - 2) { int mn = get(); sum -= saz[mn - 1].first; br--; fen_ubaci(mn, -1); v.push_back({ind, mn}); } else { v.push_back({ind, 0}); } } void rollback () { int ind = v.back().first, mn = v.back().second; //cout << "rollback " << ind << " " << mn << endl; v.pop_back(); if (mn) { sum += saz[mn - 1].first; br++; fen_ubaci(mn, 1); } sum -= p[ind].first; br--; fen_ubaci(pos[ind], -1); } void calc (int lef, int rig, int lo, int hi) { if (lef > rig) return; //cout << "calc " << lef << " " << rig << " " << lo << " " << hi << endl; int mid = (lef + rig) / 2; //cout << "mid je " << mid << endl; for (int i = max(hi + 1, lef); i < mid; i++) { ubaci(i); } llint res = -INF, piv = -1; for (int i = min(mid - 1, hi); i >= lo; i--) { if (br == m - 2) { llint tmp = sum + p[i].first + p[i].second; if (tmp > res) { res = tmp; piv = i; } } ubaci(i); } //cout << "piv je " << piv << endl; sol = max(sol, res + p[mid].first - p[mid].second); for (int i = lo; i <= min(mid - 1, hi); i++) rollback(); if (hi < mid) ubaci(mid); calc(mid + 1, rig, piv, hi); if (hi < mid) rollback(); for (int i = max(hi + 1, lef); i < mid; i++) rollback(); for (int i = piv + 1; i <= min(lef - 1, hi); i++) ubaci(i); calc(lef, mid - 1, lo, piv); for (int i = piv + 1; i <= min(lef - 1, hi); i++) rollback(); } void sazmi () { sort(saz.begin(), saz.end()); for (int i = 0; i < n; i++) { int ind = saz[i].second; pos[ind] = i + 1; } } int main () { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 0; i < n; i++) { cin >> p[i].first >> p[i].second; p[i].second *= 2; } sort(p, p + n, cmp); for (int i = 0; i < n; i++) { saz.push_back({p[i].first, i}); } sazmi(); calc(m - 1, n - 1, 0, n - 1); cout << sol; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...