제출 #1345256

#제출 시각아이디문제언어결과실행 시간메모리
1345256ElayV13Art Exhibition (JOI18_art)C++20
100 / 100
297 ms15920 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int INF=1e18;

int n;
vector<pair<int,int>>aw;

signed main() 
{
  cin>>n;
  aw.resize(n);
  for(int i=0;i<n;i++) cin>>aw[i].first>>aw[i].second;
  sort(aw.begin(),aw.end());
  vector<int>p(n);
  p[0]=aw[0].second;
  for(int i=1;i<n;i++) p[i]=p[i-1]+aw[i].second;
  vector<int>smx(n,-INF);
  smx[n-1]=p[n-1]-aw[n-1].first;
  for(int i=n-2;i>=0;i--) smx[i]=max(smx[i+1],p[i]-aw[i].first);
  int res=-INF;
  for(int i=0;i<n;i++){
    int mns=((!i)?0:p[i-1]);
    int ii=aw[i].first-mns;
    int jj=smx[i];
    res=max(res,ii+jj);
  }
  cout<<res<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...