Submission #1314893

#TimeUsernameProblemLanguageResultExecution timeMemory
1314893yeulerArt Exhibition (JOI18_art)C++20
100 / 100
144 ms12172 KiB
#include <bits/stdc++.h>
#define ll long long
#define pb emplace_back
#define fi first
#define se second
#define banyak int tc = 1; cin >> tc; while(tc--){solve();}
#define vector2d(x) vector<vector<x>>
#define pii pair<int, int>
#define pl pair<ll, ll>
#define kagamine_len ios_base::sync_with_stdio(0); cin.tie(0);
#define file_in freopen("input.txt", "r", stdin);
#define file_out freopen("output.txt", "w", stdout);
#define all(x) x.begin(), x.end()

using namespace std;

int main(){
    kagamine_len

    ll n; cin >> n;
    vector<ll> pf(n+1, 0);
    vector<pl> ar(n);
    for (ll i = 0; i < n; i++) cin >> ar[i].fi >> ar[i].se;

    sort(all(ar));
    for (ll i = 0; i < n; i++) pf[i+1] = pf[i] + ar[i].se;

    // ll ans = 0;

    // for (ll i = 0; i < n; i++){
    //     for (ll j = i; j < n; j++){
    //         ans = max(ans, pf[j+1]-pf[i]-(ar[j].fi-ar[i].fi));
    //     }
    // }

    // vector<ll> seg(4*n + 1, 1e18);
    // function<ll(ll, ll, ll)> que = [&](ll l, ll r, )

    ll mi = 1e18, ans = 0;
    for (ll i = 1; i <= n; i++){
        ll cur = i-1;
        mi = min(mi, pf[i-1]-ar[cur].fi);
        ans = max(ans, pf[i]-ar[cur].fi - mi);
    }

    // for (ll i = 1; i <= n; i++){
    //     cout << pf[i] << " ";
    // }

    /*

    pf[j+1]-pf[i]-(ar[j].fi-ar[i].fi)
    = pf[j+1]-ar[j] - pf[i]+ar[i]

    saatnya segtree :Ppppppppp

    gausa ding
    
    */

    cout << ans << "\n";


    return 0;
}


/*

misal ada s1 dan s2 sebagai a_max dan a_min
it's optimal to choose the prefix


*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...