Submission #1358504

#TimeUsernameProblemLanguageResultExecution timeMemory
1358504thesenArt Exhibition (JOI18_art)C++20
100 / 100
385 ms39552 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define vll vector<ll>
#define vbool vector<bool>
#define pairll pair<ll, ll>
#define pb push_back
#define fi first
#define sc second

const ll md = 1e9+7;
void solve(){
    ll n; cin >> n;
    vector<pairll> a(n+1); for(ll i = 1; i <= n; i++) cin >> a[i].fi >> a[i].sc;
    sort(a.begin(), a.end());

    a[0].fi = a[1].fi;
    vll p(n+1), pf(n+1);
    multiset<ll, greater<ll>> ms;
    for(ll i = 1; i <= n; i++){
        p[i] = a[i].sc - (a[i].fi - a[i-1].fi);
        pf[i] = pf[i-1] + p[i];
        ms.insert(pf[i]);
        // cout << pf[i] << ' ';
    }//cout << endl;

    ll res = 0;
    ll tot = 0;
    for(ll i = 1; i <= n; i++){
        res = max(res, tot + *ms.begin());
        tot += a[i+1].fi - a[i].fi;
        tot -= a[i].sc;
        ms.erase(ms.find(pf[i]));
    }cout << res << endl;
    
}

int main(){
    ll t = 1; //cin >> t;
    while(t--)solve();
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...