Submission #694018

#TimeUsernameProblemLanguageResultExecution timeMemory
694018Nahian9696Art Exhibition (JOI18_art)C++17
100 / 100
189 ms44264 KiB
#include <bits/stdc++.h>

using namespace std;


#define int                 int64_t
#define f0(i, n)            for(int32_t i = 0; i <  (n); i++)
#define f1(i, n)            for(int32_t i = 1; i <= (n); i++)

#define inp(x)              int x; cin >> x
#define inp2(a, b)          int a, b; cin >> a >> b

#define ff                  first
#define ss                  second





void solve1() {
    inp(n);
    int A[n], B[n];
    pair<int, int> ab[n];

    f0(i,n) {
        cin >> ab[i].ff >> ab[i].ss;
    }

    sort(ab, ab+n);

    f0(i, n) A[i] = ab[i].ff, B[i] = ab[i].ss;

    int pref[n+1] = {0};
    f1(i, n) pref[i] = pref[i-1] + B[i-1];
    int indi[n];

    f0(i,n) {
        indi[i] = pref[i+1] - A[i];
    }

    pair<int, int> sufmx[n+1];
    sufmx[n] = {0, -1};

    for(int i = n-1; i >= 0; i--) {
        if(indi[i] > sufmx[i+1].ff) {
            sufmx[i] = {indi[i], i};
        } else {
            sufmx[i] = sufmx[i+1];
        }
    }

    int ans = 0;

    f0(i, n) {
        int j = sufmx[i].ss;
        ans = max(ans, pref[j+1] - pref[i] - A[j] + A[i]);
    }
    cout << ans << endl;
}

void solve2() {
    inp(n);
    int A[n], B[n];
    pair<int, int> ab[n];

    f0(i,n) {
        cin >> ab[i].ff >> ab[i].ss;
    }

    sort(ab, ab+n);

    f0(i, n) A[i] = ab[i].ff, B[i] = ab[i].ss;

    int pref[n+1] = {0};
    f1(i, n) pref[i] = pref[i-1] + B[i-1];
    int indi[n];

    f0(i,n) {
        indi[i] = pref[i+1] - A[i];
    }

    pair<int, int> sufmx[n+1];
    sufmx[n] = {-1e18, -1};

    for(int i = n-1; i >= 0; i--) {
        if(indi[i] > sufmx[i+1].ff) {
            sufmx[i] = {indi[i], i};
        } else {
            sufmx[i] = sufmx[i+1];
        }
    }

    int ans = 0;

    f0(i, n) {
        int j = sufmx[i].ss;
        ans = max(ans, int64_t(pref[j+1] - pref[i] - A[j] + A[i]));
        // cout << j;
    }
    cout << ans << endl;
}


int32_t main() {

    #if __has_include("LOCAL.hh")
        #include "LOCAL.hh"
    #endif

    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #else
        ios_base::sync_with_stdio(0);
        cin.tie(0);
    #endif

    solve2();

    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...