Submission #1264044

#TimeUsernameProblemLanguageResultExecution timeMemory
1264044piolkArt Exhibition (JOI18_art)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h>
using namespace std;

using ll=long long;

ll compute(ll sum,ll min,ll max){
    return sum-(max-min);
}

int main(){
    int n;
    cin>>n;

    vector<pair<ll,ll>> paintings(n);

    for (int i=0;i<n;i++){
        ll a,b;
        cin>>a>>b;
        paintings[i]={a,b};
    }

    sort(paintings.begin(),paintings.end());

    ll l=0;
    ll r=-1;

    ll ans=0;
    ll sum=0;
    ll min=paintings[l].first;
    ll maxx=0;

    while (r<n-1){
        r++;
        sum+=paintings[r].second;
        maxx=paintings[r].first;

        ll now=compute(sum,min,maxx);

        ans=max(ans,now);

        ll sumWithoutL=sum-paintings[l].second;
        ll minWithoutL=paintings[l+1].first;

        ll ansWithoutL=compute(sumWithoutL,minWithoutL,maxx);

        while (l<r && ansWithoutL>now){
            sum=sumWithoutL;
            min=minWithoutL;
            l++;

            sumWithoutL=sum-paintings[l].second;
            minWithoutL=paintings[l+1].first;
            ansWithoutL=compute(sumWithoutL,minWithoutL,maxx);
        }

        ans=max(ans,compute(sum,min,maxx));
    }

    cout<<ans;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...