Submission #746433

#TimeUsernameProblemLanguageResultExecution timeMemory
746433ibshaArt Exhibition (JOI18_art)C++17
50 / 100
1082 ms8648 KiB
/*
                                  ⢀⡴⠑⡄⠀⠀⠀⠀⠀⠀⠀⣀⣀⣤⣤⣤⣀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
                                  ⠸⡇⠀⠿⡀⠀⠀⠀⣀⡴⢿⣿⣿⣿⣿⣿⣿⣿⣷⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀
                                  ⠀⠀⠀⠀⠑⢄⣠⠾⠁⣀⣄⡈⠙⣿⣿⣿⣿⣿⣿⣿⣿⣆⠀⠀⠀⠀⠀⠀⠀⠀
                                  ⠀⠀⠀⠀⢀⡀⠁⠀⠀⠈⠙⠛⠂⠈⣿⣿⣿⣿⣿⠿⡿⢿⣆⠀⠀⠀⠀⠀⠀⠀
                                  ⠀⠀⠀⢀⡾⣁⣀⠀⠴⠂⠙⣗⡀⠀⢻⣿⣿⠭⢤⣴⣦⣤⣹⠀⠀⠀⢀⢴⣶⣆
                                  ⠀⠀⢀⣾⣿⣿⣿⣷⣮⣽⣾⣿⣥⣴⣿⣿⡿⢂⠔⢚⡿⢿⣿⣦⣴⣾⠁⠸⣼⡿
                                  ⠀⢀⡞⠁⠙⠻⠿⠟⠉⠀⠛⢹⣿⣿⣿⣿⣿⣌⢤⣼⣿⣾⣿⡟⠉⠀⠀⠀⠀⠀
                                  ⠀⣾⣷⣶⠇⠀⠀⣤⣄⣀⡀⠈⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀⠀
                                  ⠀⠉⠈⠉⠀⠀⢦⡈⢻⣿⣿⣿⣶⣶⣶⣶⣤⣽⡹⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀⠀
                                  ⠀⠀⠀⠀⠀⠀⠀⠉⠲⣽⡻⢿⣿⣿⣿⣿⣿⣿⣷⣜⣿⣿⣿⡇⠀⠀⠀⠀⠀⠀
                                  ⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣷⣶⣮⣭⣽⣿⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀
                                  ⠀⠀⠀⠀⠀⠀⣀⣀⣈⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⠀⠀⠀⠀⠀⠀⠀
                                  ⠀⠀⠀⠀⠀⠀⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⠀⠀⠀⠀⠀⠀⠀⠀
                                  ⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀
                                  ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠛⠻⠿⠿⠿⠿⠛⠉
*/
#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define MOD 1000000007ll
#define endl '\n'
#define pb(v,i) (v).push_back(i)
#define vll vector<ll>
#define pll pair<ll,ll>
typedef long long ll;



__int128 fastpow(ll base,ll exp){__int128 result=1;while (exp){if (exp%2==1) result*=base;exp/=2;base*=base;}return result;}
bool isprime(ll x){for (ll i=2;i*i<=x;i++){if (x%i==0) return 0;}return 1;}
// bool issorted(auto i, auto j){ i++; for (;i!=j;i++){if (*i<*(i-1)) return 0;}return 1;}
bool cmp(ll i, ll j){ return i>j;};
bool cmp2(ll i, ll j){ // for task specific sorts
  if (i%2==j%2) return i<j;
  else if (i%2==0) return true;
  else return false;
}

ll arr[1000000];

signed main(){


  fastio
  ll n;
  cin >> n;
  pll a[n];
  for (int i=0;i<n;i++){
    cin >> a[i].first >> a[i].second;
  }
  sort(a,a+n);
  ll ans=0;
  for (int i=1;i<n;i++){
    a[i].second+=a[i-1].second;
  }
  for (int i=0;i<n;i++){
    ll l=0,r=i;
    ll curans=0;
    while (r<n){
      if (l) curans=max(curans,a[r].second-a[l-1].second-(a[r].first-a[l].first));
      else curans=max(curans,a[r].second-(a[r].first-a[l].first));
      l++;
      r++;
    }
    ans=max(ans,curans);
  }
  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...