Submission #128937

#	Time	Username	Problem	Language	Result	Execution time	Memory
128937		Plurm	Cake 3 (JOI19_cake3)	C++11	0 / 100	2 ms	256 KiB

cake3

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    int v,c;
    vector<pair<int,int> > pieces;
    for(int i = 0; i < n; i++){
        scanf("%d%d",&v,&c);
        pieces.emplace_back(v,c);
    }
    sort(pieces.begin(), pieces.end(), [](pair<int,int> x, pair<int,int> y){
        return x.second < y.second;
    });
    set<pair<int,int> > s;
    long long ans = -1e18;
    long long cur = 0ll;
    for(int i = 0; i < m; i++){
        s.insert(pieces[i]);
        cur += 1ll * pieces[i].first;
    }
    cur -= 2ll * pieces[m-1].second;
    cur += 2ll * pieces[0].second;
    int l = 0;
    int r = m-1;
    for(int i = m; i < n; i++){
        // Case 1: Remove min
        long long test1 = cur;
        test1 -= 1ll * s.begin()->first;
        test1 += 1ll * pieces[i].first;
        test1 += 2ll * pieces[r].second;
        test1 -= 2ll * pieces[i].second;
        // Case 2: Remove left
        long long test2 = cur;
        int newl = l;
        s.erase(pieces[l]);
        while(!s.count(pieces[newl])) newl++;
        s.insert(pieces[l]);
        test2 -= 1ll * pieces[l].first;
        test2 += 1ll * pieces[i].first;
        test2 += 2ll * pieces[r].second;
        test2 -= 2ll * pieces[i].second;
        test2 -= 2ll * pieces[l].second;
        test2 += 2ll * pieces[newl].second;
        // Case 3: Do nothing
        long long test3 = cur;
        long long best = max(max(test1, test2), test3);
        if(test2 == best){
            s.erase(pieces[l]);
            s.insert(pieces[i]);
            l = newl;
            r = i;
        }else if(test1 == best){
            s.erase(s.begin());
            s.insert(pieces[i]);
            r = i;
        }
        cur = best;
        ans = max(ans, cur);
    }
    printf("%lld\n",ans);
    return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:5:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
cake3.cpp:9:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&v,&c);
         ~~~~~^~~~~~~~~~~~~~

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