// 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-1); 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, 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(0, n, 0, n-1);
cout << *max_element(dp.begin(), dp.end()) << "\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... |