Submission #788216

#	Time	Username	Problem	Language	Result	Execution time	Memory
788216		1075508020060209tc	Cake 3 (JOI19_cake3)	C++14	24 / 100	4035 ms	9728 KiB

cake3

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
int n;int m;
int ans;
pair<int,int>ar[500005];

void solve(int st){
multiset<int>mst;
int sum=0;
for(int i=st-1;i>=st-m+2;i--){
    mst.insert(ar[i].second);
    sum+=ar[i].second;
}
for(int i=st-m+1;i>=1;i--){
    int cal=sum+ar[st].second-ar[st].first*2;
    cal+=ar[i].first*2+ar[i].second;
    ans=max(ans,cal);
    mst.insert(ar[i].second);
    sum+=ar[i].second;
    sum-=*(mst.begin());
    mst.erase(mst.begin());
}
}


signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
    cin>>ar[i].second>>ar[i].first;
}
sort(ar+1,ar+n+1);

ans=-1e12;
for(int i=m;i<=n;i++){
    solve(i);
}
cout<<ans<<endl;

}

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