Submission #863104

#TimeUsernameProblemLanguageResultExecution timeMemory
863104efedmrlrArt Exhibition (JOI18_art)C++17
100 / 100
175 ms30792 KiB
#include <bits/stdc++.h>

using namespace std;

#define int long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int (i) = 0; (i) < (n); (i)++)

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e17+500;
const int N = 1e5+5;
const int M = 3e5+5;
const int ALPH = 26;
const int LGN = 25;
const int MOD = 1e9+7;
int n,m,q;
vector<array<int,2> > arr; // sz, price
vector<int> pref;



inline void solve() {
    cin>>n;
    arr.resize(n);
    for(int i = 0; i<n; i++) {
        cin >> arr[i][0] >> arr[i][1];
    }
    arr.pb({0,0});
    sort(arr.begin(), arr.end());
    pref.resize(n+1);
    pref[0] = 0;
    for(int i = 1; i<=n; i++) {
        pref[i] = pref[i-1] + arr[i][1];
    }
    int mx = -INF;
    int ans = -INF;
    for (int i = n; i >= 1; i--)
    {
        mx = max(mx, pref[i] - arr[i][0]);
        ans = max(ans, mx + arr[i][0] - pref[i-1]);
    }
    cout<<ans<<"\n";
    

}
 
signed main() {
    fastio();
    int test = 1;
    //cin>>test;
    while(test--) {
        solve();
    }
    
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...