Submission #164877

#TimeUsernameProblemLanguageResultExecution timeMemory
164877cbertramArt Exhibition (JOI18_art)C++14
100 / 100
415 ms24824 KiB
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
#define all(x) x.begin(), x.end()
#define rep(i,a,b) for(int i = a; i < b; i++)

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int N;
  cin >> N;
  vpll P(N);
  rep(n,0,N) {
    ll a, b;
    cin >> a;
    cin >> b;
    P[n] = make_pair(a, b);
  }
  sort(all(P));
  rep(n,1,N) P[n].second += P[n-1].second;
  vll maxMin(N);
  maxMin[0] = P[0].first;
  rep(n,1,N) maxMin[n] = max(maxMin[n-1], P[n].first - P[n-1].second);
  ll maxHit = 0;
  rep(n,0,N) maxHit = max(maxHit, maxMin[n] - P[n].first + P[n].second);
  cout << maxHit << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...