Submission #1149996

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149996		onbert	Cake 3 (JOI19_cake3)	C++20	0 / 100	166 ms	327680 KiB

cake3

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 5, maxN = 8e5 + 5, INF = 1e18;
int n, m;
pair<int,int> a[maxn];

vector<int> L[maxN], R[maxN];
int ans = -INF;

void dnc(int id, int l, int r) {
    int sz = min(r - l + 1, m);
    if (l == r) {
        L[id] = {-a[l].first * 2, a[l].second - a[l].first * 2};
        R[id] = {a[l].first * 2, a[l].second + a[l].first * 2};
        // cout << l << " " << r << endl;
        // cout << L[id][0] << " " << L[id][1] << endl;
        // cout << R[id][0] << " " << R[id][1] << endl;
        return;
    }
    int mid = (l+r)/2;
    dnc(id*2, l, mid); dnc(id*2+1, mid+1, r);
    int lsz = L[id*2].size() - 1, rsz = L[id*2+1].size() - 1;
    for (int i=0;i<=m;i++) {
        if (i <= lsz && m-i <= rsz) ans = max(R[id*2][i] + L[id*2+1][m-i], ans);
        // if (i <= lsz && m-i <= rsz) cout << "wtf " << l << " " << r << " " << i << " " << R[id*2][i] << " " << L[id*2+1][m-i] << " " << R[id*2][i] + L[id*2+1][m-i] << endl;
        // if (i <= lsz && m-i <= rsz) if (R[id*2][i] + L[id*2+1][m-i] == 568584951) {
        //     cout << id << " " << l << " " << r << " " << endl;
        //     cout << i << " " << R[id*2][i] << " " << L[id*2+1][m-i] << endl;
        // }
    }


    vector<int> vec;
    for (int i=l;i<=mid;i++) vec.push_back(a[i].second);
    sort(vec.rbegin(), vec.rend());
    while (vec.size() > sz) vec.pop_back();
    reverse(vec.begin(), vec.end());
    vec.push_back(0);
    reverse(vec.begin(), vec.end());
    int vsz = vec.size();
    for (int i=1;i<vsz;i++) vec[i] += vec[i-1];
    // if (sz == 2) for (int i:vec) cout << i << " "; cout << endl;
    vector<pair<int,int>> pos = {{0, 0}};
    for (int i=1;i<=rsz;i++) {
        int ll = 0, rr = pos.size() - 1;
        while (ll < rr) {
            int midd = (ll+rr+1)/2;
            auto [f, s] = pos[midd];
            // if (l == 5 && r == 8 && i == 2) cout << ll << " " << rr << " " << midd << endl;
            if (f-i < 0 || L[id*2+1][i] + vec[f-i] < L[id*2+1][s] + vec[f-s]) ll = midd;
            else rr = midd-1;
        }
        // cout << "test\n";
        auto [F, S] = pos[ll];
        // if (l == 5 && r == 8) cout << "lll " << i << " " << ll << endl;
        while (pos.size() > ll+1) pos.pop_back();
        ll = max(pos[ll].first, i), rr = sz;
        // if (l == 5 && r == 8) cout << "ll " << i << " " << ll << endl;
        while (ll < rr) {
            int midd = (ll+rr)/2;
            if (midd-S >= vsz || (midd-i < vsz && L[id*2+1][i] + vec[midd-i] > L[id*2+1][S] + vec[midd-S])) rr = midd;
            else ll = midd + 1;
        }
        // if (l == 5 && r == 8) cout << "ll " << i << " " << ll << endl;
        if (ll - S >= vsz || (ll-i < vsz && L[id*2+1][i] + vec[ll-i] > L[id*2+1][S] + vec[ll-S])) {
            if (pos.back().first == ll) pos.pop_back();
            pos.push_back({ll, i});
        }
    }
    L[id].resize(sz+1);
    int pt = -1, cur;
    for (int i=0;i<=sz;i++) {
        while (pt+1 < pos.size() && pos[pt+1].first == i) pt++, cur = pos[pt].second;
        L[id][i] = L[id*2+1][cur] + vec[i-cur];
        if (i <= lsz) L[id][i] = max(L[id*2][i], L[id][i]);
    }
    if (l == 5 && r == 8) {
        
    }


    vec.clear();
    for (int i=mid+1;i<=r;i++) vec.push_back(a[i].second);
    sort(vec.rbegin(), vec.rend());
    while (vec.size() > sz) vec.pop_back();
    reverse(vec.begin(), vec.end());
    vec.push_back(0);
    reverse(vec.begin(), vec.end());
    vsz = vec.size();
    for (int i=1;i<vsz;i++) vec[i] += vec[i-1];
    pos = {{0, 0}};
    for (int i=1;i<=lsz;i++) {
        int ll = 0, rr = pos.size() - 1;
        while (ll < rr) {
            int midd = (ll+rr+1)/2;
            auto [f, s] = pos[midd];
            if (f-i < 0 || R[id*2][i] + vec[f-i] < R[id*2][s] + vec[f-s]) ll = midd;
            else rr = midd-1;
        }
        auto [F, S] = pos[ll];
        while (pos.size() > ll+1) pos.pop_back();
        ll = max(pos[ll].first, i), rr = sz;
        while (ll < rr) {
            int midd = (ll+rr)/2;
            if (midd-S >= vsz || (midd-i < vsz && R[id*2][i] + vec[midd-i] > R[id*2][S] + vec[midd-S])) rr = midd;
            else ll = midd + 1;
        }
        if (ll-S >= vsz || (ll-i < vsz && R[id*2][i] + vec[ll-i] > R[id*2][S] + vec[ll-S])) {
            if (pos.back().first == ll) pos.pop_back();
            pos.push_back({ll, i});
        }
        // if (l == 1 && r == 3) {
        //     cout << i << endl;
        //     for (auto [x, y]:pos) cout << x << " " << y << endl;
        // }
    }
    R[id].resize(sz+1);
    pt = -1;
    for (int i=0;i<=sz;i++) {
        while (pt+1 < pos.size() && pos[pt+1].first == i) pt++, cur = pos[pt].second;
        R[id][i] = R[id*2][cur] + vec[i-cur];
        // if (l==1 && r==3) cout << "13 " << i << " " << cur << " " << R[id*2][cur] << " " << vec[i-cur] << " " << L[id*2+1][cur] + vec[i-cur] << endl;
        if (i <= rsz) R[id][i] = max(R[id*2+1][i], R[id][i]);
    }
    // if (sz >= 2) {
    //     cout << l << " " << r << endl;
    //     for (int i=0;i<=sz;i++) cout << L[id][i] << " "; cout << endl;
    //     for (int i=0;i<=sz;i++) cout << R[id][i] << " "; cout << endl;
    // }
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    freopen("in.txt", "r", stdin);
    cin >> n >> m;
    for (int i=1;i<=n;i++) cin >> a[i].second >> a[i].first;
    sort(a+1, a+n+1);
    dnc(1, 1, n);
    cout << ans << "\n";
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:135:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |     freopen("in.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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