Submission #1209124

#TimeUsernameProblemLanguageResultExecution timeMemory
1209124anonymous321Tricks of the Trade (CEOI23_trade)C++20
0 / 100
8089 ms13892 KiB
// https://oj.uz/problem/view/CEOI23_trade #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = numeric_limits<ll>::max()/4; int n, k; vector<ll> vc, vs; vector<ll> p; multiset<ll> ds1 {}; multiset<ll> ds2 {}; int ds_l = 0, ds_r = -1; ll ds_val = 0; vector<ll> dp; void ds_add (int i) { if (ds1.size() < k) { ds1.insert(vs[i]); ds_val += vs[i]; } else { ds2.insert(vs[i]); } } void ds_remove (int i) { if (ds2.count(vs[i]) > 0) { ds2.erase(ds2.find(vs[i])); } else if (ds1.count(vs[i]) > 0) { ds1.erase(ds1.find(vs[i])); ds_val -= vs[i]; if (ds2.size() > 0) { auto it = prev(ds2.end()); ds_val += *it; ds1.insert(*it); ds2.erase(it); } } } void ds_move (int lo, int hi) { // lo, hi inclusive while (ds_r < hi) { ds_r++; ds_add(ds_r); } while (ds_l > lo) { ds_l--; ds_add(ds_l); } while (ds_r > hi) { ds_remove(ds_r); ds_r--; } while (ds_l < lo) { ds_remove(ds_l); ds_l++; } } void calc (int l, int r, int optl, int optr) { if (l > r) return; int mid = (l + r) / 2; int nopt = -1; for (int i = optl; i <= min(optr, mid); i++) { ds_move(i, mid); if (ds1.size() == k) { ll x = ds_val + p[mid+1] - p[i]; if (dp[mid] < x) { dp[mid] = x ; nopt = i; } } } if (nopt == -1) { calc (mid+1, r, optl, optr); } else { calc (l, mid-1, optl, nopt); calc (mid+1, r, nopt, optr); } } int main() { cin >> n >> k; vc = vector<ll> (n); for (int i = 0; i < n; i++) { cin >> vc[i]; } vs = vector<ll> (n); for (int i = 0; i < n; i++) { cin >> vs[i]; } p = vector<ll> (n+1, 0); for (int i = 0; i < n; i++) { p[i+1] = p[i] - vc[i]; } dp = vector<ll> (n, -INF); calc(k-1, n-1, 0, n-1); cout << *max_element(dp.begin(), dp.end()) << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...