Submission #1209108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209108		Hamed_Ghaffari	Cake 3 (JOI19_cake3)	C++20	100 / 100	2951 ms	13812 KiB

cake3

#include <bits/stdc++.h>
using namespace std;

using ll  = long long;
using pii = pair<int, int>;

#define SZ(x) int(x.size())
#define X first
#define Y second
#define mid ((l+r)>>1)

const int MXN = 2e5+5;

int n, m, V[MXN], C[MXN];

struct DS {
    set<pii> s1, s2;
    ll sum;
    DS(): sum(0) {}
    inline void insert(pii x) {
        sum += x.X;
        s2.insert(x);
        if(SZ(s2)==m+1) {
            sum -= s2.begin()->X;
            s1.insert(*s2.begin());
            s2.erase(s2.begin());
        }
    }
    inline void erase(pii x) {
        if(s1.find(x)!=s1.end()) s1.erase(x);
        else {
            sum -= x.X;
            s2.erase(x);
            if(SZ(s2)<m && !s1.empty()) {
                sum += s1.rbegin()->X;
                s2.insert(*s1.rbegin());
                s1.erase(prev(s1.end()));
            }
        }
    }
} ds;

int L, R;

inline void add(int i) { ds.insert({V[i], i}); }

inline void rem(int i) { ds.erase({V[i], i}); }

inline void adjust(int l, int r) {
    while(R<r) add(++R);
    while(L>l) add(--L);
    while(R>r) rem(R--);
    while(L<l) rem(L++);
}

inline ll cost() { return ds.sum - 2*C[R] + 2*C[L]; }

ll dp[MXN];
int opt[MXN];

void rec(int l, int r, int opl, int opr) {
    if(l>r) return;
    dp[mid] = -1e18;
    for(int i=max(opl, mid+m-1); i<=opr; i++) {
        adjust(mid, i);
        if(cost()>dp[mid]) {
            dp[mid] = cost();
            opt[mid] = i;
        }
    }
    rec(mid+1, r, opt[mid], opr);
    rec(l, mid-1, opl, opt[mid]);
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> m;
    vector<pii> vec(n);
    for(int i=0; i<n; i++)
        cin >> vec[i].Y >> vec[i].X;
    sort(vec.begin(), vec.end());
    for(int i=0; i<n; i++)
        V[i+1] = vec[i].Y, C[i+1] = vec[i].X;
    L = 1;
    rec(1, n+1-m, 1, n);
    cout << *max_element(dp+1, dp+n+2-m) << '\n';
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 76 / 76