제출 #1142724

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1142724		VMaksimoski008	Cake 3 (JOI19_cake3)	C++20	100 / 100	1070 ms	207932 KiB

cake3

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e5 + 5;

vector<int> comp;

struct node {
    int cnt = 0;
    ll sum = 0;
    node *l, *r;

    node(int c=0, ll v=0) : cnt(c), sum(v), l(nullptr), r(nullptr) {}
    node(node *l, node *r) : l(l), r(r) {
        if(l) sum += l->sum, cnt += l->cnt;
        if(r) sum += r->sum, cnt += r->cnt;
    }
};

node *build(int l, int r) {
    if(l == r) return new node(0, 0);
    int tm = (l + r) / 2;
    return new node(build(l, tm), build(tm+1, r));
}

node *update(node *u, int tl, int tr, int p) {
    if(tl == tr) return new node(u->cnt + 1, u->sum + comp[p]);
    int tm = (tl + tr) / 2;
    if(p <= tm) return new node(update(u->l, tl, tm, p), u->r);
    return new node(u->l, update(u->r, tm+1, tr, p));
}

int n, m; ll ans = -1e18;
vector<array<int, 2> > a(maxn);
vector<node*> R;

ll find(node *u, node *v, int tl, int tr, int k) {
    if(tl == tr) return 1ll * k * comp[tl];
    int tm = (tl + tr) / 2;
    if(u->r->cnt - v->r->cnt >= k) return find(u->r, v->r, tm+1, tr, k);
    return u->r->sum - v->r->sum + find(u->l, v->l, tl, tm, k - (u->r->cnt - v->r->cnt));
}

ll query(int l, int r, int k) {
    return find(R[r], R[l-1], 1, n, k);
}

void dnc(int l, int r, int optL, int optR) {
    if(l > r) return ;
    int tm = (l + r) / 2, p = optL;
    ll best = -1e18;

    for(int i=optL; i+m-1<=tm&&i<=optR; i++) {
        ll val = a[tm][1] + a[i][1] + 2ll * (a[i][0] - a[tm][0]) + query(i+1, tm-1, m-2);
        if(val > best) best = val, p = i;
    }

    ans = max(ans, best);
    dnc(l, tm-1, optL, p);
    dnc(tm+1, r, p, optR);
}

int main() {
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> a[i][1] >> a[i][0];
    sort(a.begin()+1, a.begin()+n+1);

    set<int> st; st.insert(-1);
    for(int i=1; i<=n; i++) st.insert(a[i][1]);
    comp = vector<int>(st.begin(), st.end());

    R.push_back(build(1, n));
    for(int i=1; i<=n; i++) {
        int p = lower_bound(comp.begin(), comp.end(), a[i][1]) - comp.begin();
        R.push_back(update(R[i-1], 1, n, p));
    }

    dnc(m, n, 1, n);
    cout << ans << '\n';
}

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