제출 #1178452

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1178452		peteza	Cake 3 (JOI19_cake3)	C++20	0 / 100	0 ms	320 KiB

cake3

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

int n, k;
vector<pair<int, int>> vec;

struct node {
    ll sum = 0; int cnt = 0;
    node *l, *r;
    node(node *_l, node *_r): l(_l), r(_r), sum(_l->sum + _r->sum), cnt(_l->cnt + _r->cnt) {}
    node(): cnt(0), sum(0) {}
    node(ll x):cnt(1), sum(x) {}
} *roots[200005];

node* build(int l, int r) {
    if(l == r) return new node();
    int mid = (l+r) >> 1;
    return new node(build(l, mid), build(mid+1, r));
}

node* upd(node*&cur, int l, int r, int tgt, ll val) {
    if(l == r) return new node(val);
    int mid = (l+r) >> 1;
    if(tgt <= mid) return new node(upd(cur->l, l, mid, tgt, val), cur->r);
    return new node(cur->l, upd(cur->r, mid+1, r, tgt, val));
}

ll qr(node *&oldl, node *& oldr, int k) {
    if(k <= 0) return 0;
    if(oldr->cnt - oldl->cnt <= k) return oldr->sum - oldl->sum;
    if(oldr->r->cnt - oldl->r->cnt >= k) return qr(oldl->r, oldr->r, k);
    return qr(oldl->l, oldr->l, k - (oldr->r->cnt - oldl->r->cnt)) + (oldr->r->sum - oldl->r->sum);
}

ll dpdc(int l, int r, int optl, int optr) {
    if(r < l) return LLONG_MIN;
    int mid = (l+r) >> 1;
    pair<int, int> bestbest(LLONG_MIN, mid);
    for(int i = max(mid, optl)+k-1; i <= optr; i++) {
        ll res = qr(roots[mid], roots[i+1], k) - vec[i].first + vec[mid].first;
        if(res > bestbest.first) bestbest = {res, i};
    }
    ll toret = bestbest.first;
    //cout << mid << " -> " << toret << '\n';
    return max({toret, dpdc(l, mid-1, optl, bestbest.second), dpdc(mid+1, r, bestbest.second, optr)});
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> k;
    vec.resize(n);
    roots[0] = build(0, n-1);
    vector<pair<int, int>> vals; int i = 0;
    for(auto &e:vec) {
        cin >> e.second >> e.first;
        e.first *= 2;
    }
    sort(vec.begin(), vec.end());
    for(auto &e:vec) vals.emplace_back(e.second, i++);
    sort(vals.begin(), vals.end());
    for(int i=0;i<vec.size();i++) {
        auto it = lower_bound(vals.begin(), vals.end(), make_pair(vec[i].second, i)) - vals.begin();
        assert(vec[i].second == vals[it].first && i == vals[it].second);
        roots[i+1] = upd(roots[i], 0, n-1, it, vec[i].second);
    }
    //int a, b, c;
    //while(cin >> a >> b >> c) cout << qr(roots[a], roots[b+1], c) << '\n';
    cout << dpdc(0, n-1, 0, n-1);
}

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