Submission #694001

#	Time	Username	Problem	Language	Result	Execution time	Memory
694001		Nahian9696	Art Exhibition (JOI18_art)	C++17	0 / 100	0 ms	212 KiB

art

#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;
}


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

    solve1();

    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50