Submission #1014471

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014471		vjudge1	Cake 3 (JOI19_cake3)	C++17	0 / 100	1 ms	600 KiB

cake3

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<pair<int,int>> cake;
int ans;
int dostuf(int pen){
    ans=0;
    map<int,pair<int,int>>mp;
    for(auto[i,j]:cake) if(j>=pen)
        mp[i].first+=j-pen,mp[i].second--;
    if(mp.empty())return 0;
    int prv=mp.begin()->first;
    pair<int,int>mmin,now,bst;
    for(auto&[i,j]:mp) j.first-=2*i-2*prv,prv=i,
        now.first+=j.first,now.second+=j.second,mmin=min(mmin,now),
        bst=max(bst,{now.first-mmin.first,now.second-mmin.second});
    ans=bst.first;
    return -bst.second;
}
signed main(){
    int n,m;
    cin>>n>>m;
    cake.resize(n);
    for(auto&[i,j]:cake)
        cin>>j>>i;
    int l=-1e9,r=1e9,res=0;
    while(l<=r){
        int mid=l+r>>1;
        if(dostuf(mid)>=m)
            l=mid+1,res=mid;
        else r=mid-1;
    }
    dostuf(res);
    cout<<ans+res*m;
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:28:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |         int mid=l+r>>1;
      |                 ~^~

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