제출 #1127549

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127549		Zero_OP	Cake 3 (JOI19_cake3)	C++17	24 / 100	4093 ms	4584 KiB

cake3

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAX = 2e5 + 5;

int N, K;
struct cake{
    ll 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;
    priority_queue<ll, vector<ll>, greater<ll>> pq;

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

    void insert(ll x){
        if((int)pq.size() < keep){
            sum += x;
            pq.push(x);
        } else{
            ll mn = pq.top();
            if(mn < x){
                pq.pop();
                sum -= mn;
                sum += x;
                pq.push(x);
            }
        }
    }

    ll get(){
        return sum;
    }

    void reset(){
        sum = 0;
        priority_queue<ll, vector<ll>, greater<ll>>().swap(pq);
    }
};

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);

    ll ans = LLONG_MIN;
    F max_sums(K);

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

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

    cout << ans << '\n';

    return 0;
}

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