Submission #208124

#	Time	Username	Problem	Language	Result	Execution time	Memory
208124		achibasadzishvili	Cake 3 (JOI19_cake3)	C++17	0 / 100	5 ms	380 KiB

cake3

#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
using namespace std;
multiset<ll>st;
pair<ll,ll>a[200005];
ll n,m,ans=-9999999999999999;
void solve(ll l,ll r,ll x,ll y){
    l = max(l , x + m - 1);
    if(l > r || y < x + m - 1)return;
    ll k = (l + r) / 2;
    ll mx = -9999999999999999 , ind = y;
    st.clear();
    ll cur = 0;
    for(int i=k; i>=x; i--){
        ll mn = 0;
        if(st.size())mn = (*st.begin());
        if(mn < a[i].s || ((int)st.size() < m)){
            cur += a[i].s;
            if(st.size() >= m){st.erase(st.begin());cur -= mn;}
            st.insert(a[i].s);
        }
        if(st.size() >= m && cur - 2 * (a[k].f - a[i].f) > mx)
                mx = cur - 2 * (a[k].f - a[i].f),
                ind = i;
    }
    if(mx == -9999999999999999)return;
    ans = max(ans , mx);
    if(l == r)return;
    solve(l , k , x , ind);
    solve(k + 1 , r , ind , y);
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    
    for(int i=1; i<=n; i++){
        cin >> a[i].s >> a[i].f;
    }
    
    sort(a + 1 , a + n + 1);
    
    solve(1 , n , 1 , n);
    
    cout << ans << '\n';
    
    
    return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'void solve(long long int, long long int, long long int, long long int)':
cake3.cpp:22:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(st.size() >= m){st.erase(st.begin());cur -= mn;}
                ~~~~~~~~~~^~~~
cake3.cpp:25:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(st.size() >= m && cur - 2 * (a[k].f - a[i].f) > mx)
            ~~~~~~~~~~^~~~

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