Submission #1209134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209134		anonymous321	Tricks of the Trade (CEOI23_trade)	C++20	10 / 100	8061 ms	13896 KiB

trade

// 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 {
        if (vs[i] <= *ds1.begin()) {
            ds2.insert(vs[i]);
        } else {
            auto it = ds1.begin();
            ds_val -= *it;
            ds2.insert(*it);
            ds1.erase(it);
            ds_val += vs[i];
            ds1.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); 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-1, 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(k-1, n-1, 0, n-1);
    cout << *max_element(dp.begin(), dp.end()) << "\n";
    return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 10
• Subtask 2: 5 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45