Submission #249457

#	Time	Username	Problem	Language	Result	Execution time	Memory
249457		dwsc	Cake 3 (JOI19_cake3)	C++14	24 / 100	4078 ms	4736 KiB

cake3

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> ii;
main(){
    int n,m;
    cin >> n >> m;
    ii arr[n];
    for (int i = 0; i < n; i++) cin >> arr[i].second >> arr[i].first;
    sort(arr,arr+n);
    int ans = -1e18;
    for (int i = 0; i+m <= n; i++){
        int sum = 0;
        priority_queue<int,vector<int>,greater<int> > pq;
        for (int j = i; j < i+m; j++){
            pq.push(arr[j].second);
            sum += arr[j].second;
        }
        ans = max(ans,sum-2*(arr[i+m-1].first-arr[i].first));
        for (int j = i+m; j < n; j++){
            int v = arr[j].second;
            if (v > pq.top()){
                sum += v-pq.top();
                pq.pop();
                pq.push(v);
                ans = max(ans,sum-2*(arr[j].first-arr[i].first));
            }
        }
    }
    cout << ans;
}

Compilation message (stderr)

cake3.cpp:5:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

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