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;
#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif
const int N = 250003;
int n, k;
int g[N];
int cl, cr;
bool ok[N];
long long s2;
int c[N], s[N];
long long dp[N];
long long pref[N];
multiset<int> se, se2;
vector<int> to_add[N], to_rem[N];
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;
}
}
}
dp[mid] = ret;
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];
}
dp[0] = -LLONG_MAX;
cl = 1, cr = 0;
long long ans = solve(k, n, 1, n);
for (int i = 1; i <= n; ++i) {
g[i] = (dp[i] == ans);
g[i] += g[i - 1];
}
for (int i = n, j = n; i >= 1; --i) {
if (dp[i] != ans) {
continue;
}
if (j > i) j = i;
int f = 0;
while (j > 0) {
edit(j, i);
int nf = g[i] - g[j - 1] - (k > 1);
long long val = pref[i] - pref[j - 1] + s2;
if (val == ans && (int) se2.size() == k) {
int mn = *se2.begin();
to_add[j].push_back(mn);
to_rem[i].push_back(mn);
f |= 2;
}
if (f && nf) {
break;
}
--j;
}
}
multiset<int> ss;
for (int i = 1; i <= n; ++i) {
for (int j : to_add[i]) {
ss.insert(j);
}
if (!ss.empty() && *ss.begin() <= s[i]) {
ok[i] = true;
}
for (int j : to_rem[i]) {
ss.erase(ss.find(j));
}
}
cout << ans << '\n';
for (int i = 1; i <= n; ++i) {
cout << ok[i];
}
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... |