Submission #1264034

#TimeUsernameProblemLanguageResultExecution timeMemory
1264034piolkArt Exhibition (JOI18_art)C++20
50 / 100
1096 ms12084 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());

    vector<ll> pSum(n);

    for (int i=0;i<n;i++){
        pSum[i]=paintings[i].second + (i>0 ? pSum[i-1] : 0);
    }

    ll ans=0;

    for (int i=0;i<n;i++){
        for (int j=0;j<=i;j++){
            ll maxx=paintings[i].first;
            ll minn=paintings[j].first;

            ll sum;
            if (j==0) sum=pSum[i];
            else sum=pSum[i]-pSum[j-1];

            ll wyn=compute(sum,minn,maxx);

            //cout<<"min: "<<minn<<" max: "<<maxx<<" sum: "<<sum<<" wynik: "<<wyn<<"\n";

            ans=max(ans,wyn);
        }
    }

    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...