Submission #1266155

#TimeUsernameProblemLanguageResultExecution timeMemory
1266155WH8Art Exhibition (JOI18_art)C++20
100 / 100
620 ms12160 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pll pair<int, int> #define mp make_pair #define pb push_back #define f first #define s second #define endl '\n' signed main(){ int n;cin>>n; vector<pair<int,int>> v(n); int ans=0; for(int i=0;i<n;i++){ cin>>v[i].f>>v[i].s; ans=max(ans,v[i].s); } sort(v.begin(),v.end()); vector<int> sfx(n, 0); sfx[n-1]=v[n-2].f-v[n-1].f+v[n-1].s; for(int i=n-2;i>=1;i--){ sfx[i]=sfx[i+1]+v[i].s-v[i].f+v[i-1].f; } //~ for(int i=1;i<n;i++){ //~ cout<<sfx[i]<<" "; //~ } //~ cout<<endl; int best=0; for(int i=n-2;i>=0;i--){ best=min(best, sfx[i+1]); ans=max(ans, v[i].s+sfx[i+1]-best); } cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...