이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif
const int N = 250003;
int n, k;
int cl, cr;
long long s2;
int c[N], s[N];
long long pref[N];
multiset<int> se, se2;
void balance() {
if ((int) se2.size() > k) {
int mn = *se2.begin();
s2 -= mn;
se.insert(mn);
se2.erase(se2.begin());
}
if ((int) se2.size() < k && !se.empty()) {
int mx = *se.rbegin();
s2 += mx;
se2.insert(mx);
se.erase(se.find(mx));
}
}
void add(int ind) {
se2.insert(s[ind]);
s2 += s[ind];
balance();
}
void rem(int ind) {
if (se2.count(s[ind])) {
s2 -= s[ind];
se2.erase(se2.find(s[ind]));
} else {
se.erase(se.find(s[ind]));
}
balance();
}
void edit(int l, int r) {
while (cl > l) add(--cl);
while (cr < r) add(++cr);
while (cl < l) rem(cl++);
while (cr > r) rem(cr--);
}
long long solve(int l, int r, int optl, int optr) {
if (l > r) {
return -LLONG_MAX;
}
int mid = (l + r) >> 1;
long long ret = -LLONG_MAX;
int opt = -1;
for (int i = min(mid, optr); i >= optl; --i) {
edit(i, mid);
if ((int) se2.size() == k) {
long long val = pref[mid] - pref[i - 1] + s2;
if (val >= ret) {
ret = val;
opt = i;
}
}
}
ret = max(ret, solve(l, mid - 1, optl, opt));
ret = max(ret, solve(mid + 1, r, opt, optr));
return ret;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> c[i];
pref[i] = pref[i - 1] - c[i];
}
for (int i = 1; i <= n; ++i) {
cin >> s[i];
}
cl = 1, cr = 0;
cout << solve(1, n, 1, n) << '\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... |