Submission #1256573

#TimeUsernameProblemLanguageResultExecution timeMemory
1256573motionArt Exhibition (JOI18_art)C++20
100 / 100
311 ms16056 KiB
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin>>n;
   vector<long long> pre;
   vector<pair<long long,long long>> v;
   pre.push_back(0);
   for(int i=0;i<n;i++)
   {
       long long a,b;
       cin>>a>>b;
       v.push_back({a,b});
   }
   sort(v.begin(),v.end());
   for(int i=0;i<n;i++)
   {
       pre.push_back(pre[i]+v[i].second);
   }
   vector<long long> ma(n,0);
   ma[n-1]=pre[n]-v[n-1].first;
   for(int i=n-2;i>=0;i--)
   {
       ma[i]=max(ma[i+1],pre[i+1]-v[i].first);
   }
   long long ans=0;
   for(int i=0;i<n;i++)
   {
       ans=max(ans,ma[i]-pre[i]+v[i].first);
   }
   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...