Submission #1264031

#TimeUsernameProblemLanguageResultExecution timeMemory
1264031piolkArt Exhibition (JOI18_art)C++20
0 / 100
0 ms320 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()); int l=0; int r=-1; ll sum=0; ll min=paintings[l].first; ll maxx=0; ll ans=0; while (r<n-1){ r++; sum+=paintings[r].second; maxx=paintings[r].first; //cout<<"now at: "<<r<<" sum is: "<<sum<<" and max is now "<<maxx<<" and min is "<<min<<"\n"; ans=max(ans,compute(sum,min,maxx)); while (l<r && compute(sum-paintings[l].second,paintings[l+1].first,maxx)>ans){ //cout<<"it's better if we exclude "<<l<<" because we will have "<<compute(sum-paintings[l].second,paintings[l+1].first,maxx)<<"\n"; sum-=paintings[l].second; l++; min=paintings[l].first; } 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...