Submission #1209240

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209240		jujuedv	Tricks of the Trade (CEOI23_trade)	C++20	50 / 100	3209 ms	17056 KiB

trade

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

constexpr ll INF = ll(1e18);
constexpr int INF_IDX = int(1e9);

int n, k;
vector<int> a, b;

struct walker {
    int i, j;

    multiset<int> biggest_k, remainder;

    ll sum_b = 0;
    ll sum_biggest_k = 0;

    walker(int x) { // interval from x to x
        i = j = x;
        add_elem(x);
    }

    ll value() {
        if(j - i + 1 >= k)
            return sum_biggest_k - sum_b;
        else
            return -INF;
    }

    void add_elem(int x) {
        sum_b += b[x];
        sum_biggest_k += a[x];
        biggest_k.insert(a[x]);

        if(biggest_k.size() > k) {
            auto it = biggest_k.begin();
            sum_biggest_k -= *it;
            remainder.insert(*it);
            biggest_k.erase(it);
        }
    }

    void remove_elem(int x) {
        sum_b -= b[x];
        if(biggest_k.count(a[x]) > 0) {
            auto it = biggest_k.find(a[x]);
            sum_biggest_k -= a[x];
            biggest_k.erase(it);
        } else {
            remainder.erase(remainder.find(a[x]));
        }

        if(biggest_k.size() < k && remainder.size() > 0) {
            auto it = --remainder.end();
            sum_biggest_k += *it;
            biggest_k.insert(*it);
            remainder.erase(it);
        }
    }

    void decrease_i() {
        add_elem(--i);
    }

    void increase_i() {
        remove_elem(i++);
    }

    void decrease_j() {
        remove_elem(j--);
    }

    void increase_j() {
        add_elem(++j);
    }

    void move(int ii, int jj) {
        while(i > ii) decrease_i();
        while(j < jj) increase_j();

        while(i < ii) increase_i();
        while(j > jj) decrease_j();
    }
};

vector<ll> best_val_starting_at;
vector<int> opt_min;

void comp_opt_min(int l, int r, int opt_lo, int opt_hi, walker& walk) {
    if(l > r) return;

    int m = (l + r)/2;
    ll best_val = -INF;
    ll opt = INF_IDX;
    for(int j = max(opt_lo, m); j <= opt_hi; ++j) {
        walk.move(m, j);
        if(walk.value() > best_val) {
            best_val = walk.value();
            opt = j;
        }
    }

    opt_min[m] = opt;
    best_val_starting_at[m] = best_val;

    if(opt == INF_IDX) opt = opt_hi; // prevent weird edge cases

    comp_opt_min(l, m-1, opt_lo, opt, walk);
    comp_opt_min(m+1, r, opt, opt_hi, walk);
}

int main() {
    cin >> n >> k;

    a.resize(n);
    b.resize(n);

    for(auto &x : b) cin >> x;
    for(auto &x : a) cin >> x;

    opt_min.resize(n);
    best_val_starting_at.resize(n);

    {
        walker walk(n/2);
        comp_opt_min(0, n-1, 0, n-1, walk);
    }

    ll max_val = -INF;
    for(int i = 0; i < n; ++i) {
        max_val = max(max_val, best_val_starting_at[i]);
    }

    cout << max_val << endl;

}

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