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>
using namespace std;
const int N = 250000;
const int MAX = (int) 1.00001e9;
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][1]] - cnt[ch[y][1]] >= k) {
return Walk(ch[x][1], ch[y][1], mid + 1, r, k);
} else {
return Walk(ch[x][0], ch[y][0], l, mid, k - (cnt[ch[x][1]] - cnt[ch[y][1]]));
}
}
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, el + 1, MAX);
ret += QuerySum(root[r], l == 0 ? 0 : root[l - 1], 0, MAX, el + 1, MAX);
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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |