Submission #1060768

#TimeUsernameProblemLanguageResultExecution timeMemory
1060768MilosMilutinovicTricks of the Trade (CEOI23_trade)C++14
0 / 100
486 ms161068 KiB
#include <bits/stdc++.h> using namespace std; const int N = 250000; const int MAX = (int) 1e9; int root[N * 60], ch[N * 60][2], cnt[N * 60], tsz; long long sum[N * 60]; void Modify(int& x, int y, int l, int r, int i) { x = ++tsz; ch[x][0] = ch[y][0]; ch[x][1] = ch[y][1]; sum[x] = sum[y] + i; cnt[x] = cnt[y] + 1; if (l == r) { return; } int mid = (l + r) >> 1; if (i <= mid) { Modify(ch[x][0], ch[y][0], l, mid, i); } else { Modify(ch[x][1], ch[y][1], mid + 1, r, i); } } int Walk(int x, int y, int l, int r, int k) { if (l == r) { return l; } int mid = (l + r) >> 1; if (cnt[ch[x][0]] - cnt[ch[y][0]] >= k) { return Walk(ch[x][0], ch[y][0], l, mid, k); } else { return Walk(ch[x][1], ch[y][1], mid + 1, r, k - (cnt[ch[x][0]] - cnt[ch[y][0]])); } } int QueryCnt(int x, int y, int l, int r, int ll, int rr) { if (ll <= l && r <= rr) { return cnt[x] - cnt[y]; } int mid = (l + r) >> 1; if (rr <= mid) { return QueryCnt(ch[x][0], ch[y][0], l, mid, ll, rr); } else if (ll > mid) { return QueryCnt(ch[x][1], ch[y][1], mid + 1, r, ll, rr); } else { return QueryCnt(ch[x][0], ch[y][0], l, mid, ll, rr) + QueryCnt(ch[x][1], ch[y][1], mid + 1, r, ll, rr); } } long long QuerySum(int x, int y, int l, int r, int ll, int rr) { if (ll <= l && r <= rr) { return sum[x] - sum[y]; } int mid = (l + r) >> 1; if (rr <= mid) { return QuerySum(ch[x][0], ch[y][0], l, mid, ll, rr); } else if (ll > mid) { return QuerySum(ch[x][1], ch[y][1], mid + 1, r, ll, rr); } else { return QuerySum(ch[x][0], ch[y][0], l, mid, ll, rr) + QuerySum(ch[x][1], ch[y][1], mid + 1, r, ll, rr); } } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, k; cin >> n >> k; vector<int> c(n); for (int i = 0; i < n; i++) { cin >> c[i]; } vector<int> s(n); for (int i = 0; i < n; i++) { cin >> s[i]; } vector<long long> pref(n); for (int i = 0; i < n; i++) { pref[i] = (i == 0 ? 0LL : pref[i - 1]) + c[i]; } for (int i = 0; i < n; i++) { if (i > 0) { root[i] = root[i - 1]; } Modify(root[i], root[i], 0, MAX, s[i]); } const long long inf = (long long) -1e18; long long res = inf; auto Calc = [&](int l, int r) { if (r - l + 1 < k) { return inf; } long long ret = -(pref[r] - (l == 0 ? 0LL : pref[l - 1])); int el = Walk(root[r], l == 0 ? 0 : root[l - 1], 0, MAX, k); int c = QueryCnt(root[r], l == 0 ? 0 : root[l - 1], 0, MAX, 0, el - 1); ret += QuerySum(root[r], l == 0 ? 0 : root[l - 1], 0, MAX, 0, el - 1); ret += el * 1LL * (k - c); return ret; }; function<void(int, int, int, int)> Solve = [&](int l, int r, int optl, int optr) { if (l > r) { return; } int mid = (l + r) >> 1; int opt = min(optl, mid); long long best = Calc(opt, mid); for (int i = optl; i <= min(mid, optr); i++) { long long v = Calc(i, mid); if (v > best) { best = v; opt = i; } } res = max(res, best); Solve(l, mid - 1, optl, opt); Solve(mid + 1, r, opt, optr); }; Solve(0, n - 1, 0, n - 1); cout << res << '\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...