Submission #824203

#TimeUsernameProblemLanguageResultExecution timeMemory
824203SoulKnightArt Exhibition (JOI18_art)C++17
100 / 100
143 ms24732 KiB
#include "bits/stdc++.h"
using namespace std;

#define ll long long
#define ln '\n'

const int N = 5e5 + 5;
const int LG = 20;
const int INF = 2e9 + 5;
const int MOD = 998244353;

int n;
pair<ll, ll> a[N];
ll pfx[N];

void init(){
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> a[i].first >> a[i].second;
    }
}

ll solve(){
    sort(a, a+n);
    pfx[0] = a[0].second;
    for (int i = 1; i < n; i++) pfx[i] = pfx[i-1] + a[i].second;
    ll ans = 0LL, mx = 0LL;

    for (int i = 0; i < n; i++){
        mx = max(mx, a[i].first - ((i-1 < 0)? 0LL: pfx[i-1]));
        ans = max(ans, pfx[i] + mx - a[i].first);
    }

    return ans;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    // freopen("mooyomooyo.in", "r", stdin);
    // freopen("mooyomooyo.out", "w", stdout);


    // ll T; cin >> T;
    // while (T--){
    //     solve();
    // }

    init();
    cout << solve();


    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...