Submission #249428

#	Time	Username	Problem	Language	Result	Execution time	Memory
249428		dantoh000	Cake 3 (JOI19_cake3)	C++14	24 / 100	4059 ms	14072 KiB

cake3

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
multiset<int> good, bad;
const ll INF = 1000000000000000;
int n,m;
ll ans = -INF;
ll sum = 0;
ii a[200005];
void balance(){
    auto G = *(good.begin());
    auto B = *(--bad.end());
    if (G < B){
        bad.insert(G);
        good.insert(B);
        sum += B-G;
        good.erase(good.begin());
        bad.erase(--bad.end());
    }
    assert(good.size() == m);
}
void add(int x){
    //printf("adding %d\n",x);
    if (good.size() < m){
        sum += x;
        good.insert(x);
        return;
    }
    bad.insert(x);
    balance();
}
bool cmp(ii a, ii b){
    return a.second < b.second;
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i = 0; i < n; i++){
        scanf("%d%d",&a[i].first,&a[i].second);
    }
    sort(a,a+n,cmp);
    for (int i = 0; i < n; i++){
        //printf("%d %d\n",a[i].first,a[i].second);
        sum = 0;
        //printf("clearing\n");
        good.clear();
        bad.clear();
        for (int j = i; j < n; j++){
            //printf("processing <%d,%d>\n",a[j].first,a[j].second);
            add(a[j].first);
            if ((int)good.size() == m){
                ans = max(ans,sum-2*(a[j].second-a[i].second));
            }
        }
    }
    printf("%lld",ans);
}

Compilation message (stderr)

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from cake3.cpp:1:
cake3.cpp: In function 'void balance()':
cake3.cpp:21:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     assert(good.size() == m);
            ~~~~~~~~~~~~^~~~
cake3.cpp: In function 'void add(int)':
cake3.cpp:25:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (good.size() < m){
         ~~~~~~~~~~~~^~~
cake3.cpp: In function 'int main()':
cake3.cpp:37: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:39:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a[i].first,&a[i].second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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