제출 #1127521

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

cake3

#include <bits/stdc++.h>

#define int long long

using namespace std;
using ll = long long;

const int MAX = 2e5 + 5;

int N, K;
struct cake{
    int V, C;
    cake() : V(0), C(0) {}
    cake(int V, int C) : V(V), C(C) {}
    bool operator < (const cake& o){
        return make_pair(C, -V) < make_pair(o.C, -o.V);
    }

    friend istream& operator >> (istream& in, cake& c){
        return in >> c.V >> c.C;
    }
} cakes[MAX];

struct F{
    int keep;
    ll sum;
    multiset<ll> A;

    F(int k) : A(), keep(k), sum(0) {}

    void insert(ll x){
        if((int)A.size() < keep){
            sum += x;
            A.insert(x);
        } else{
            ll mn = *A.begin();
            if(mn < x){
                A.erase(A.begin());
                sum -= mn;
                sum += x;
                A.insert(x);
            }
        }
    }

    ll get(){
        return sum;
    }
};

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    cin >> N >> K;
    for(int i = 1; i <= N; ++i){
        cin >> cakes[i];
    }

    sort(cakes + 1, cakes + 1 + N);

    for(int i = 2; i <= N; ++i){
        assert(cakes[i - 1].C <= cakes[i].C);
    }

    ll ans = 0;
    for(int i = 1; i + K - 1 <= N; ++i){
        F max_sums(K - 2);
        for(int j = i + 1; j <= i + K - 2; ++j){
            max_sums.insert(cakes[j].V);
        }

        for(int j = i + K - 1; j <= N; ++j){
            ans = max(ans, (ll)cakes[i].V + cakes[j].V + max_sums.get() - (cakes[j].C - cakes[i].C) * 2LL);
            max_sums.insert(cakes[j].V);
        }
    }

    cout << ans << '\n';

    return 0;
}

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