Submission #687385

#	Time	Username	Problem	Language	Result	Execution time	Memory
687385		Bliznetc	Art Exhibition (JOI18_art)	C++17	50 / 100	215 ms	38824 KiB

art

#include <bits/stdc++.h>

#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#pragma GCC target("avx2")

using namespace std;

#define pb push_back
#define sz size()
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define int long long

typedef pair < int, int > pii;
typedef vector < int >  vi;
typedef vector < vi >  vvi;

const int N = 200200;
int pref[N];
int t[4 * N];

void upd (int v, int l, int r, int pos, int val) {
    if (l > pos || r < pos) {
        return;
    }
    if (l == r) {
        t[v] = val;
        return;
    }
    int mid = (l + r) / 2;
    upd (2 * v, l, mid, pos, val);
    upd (2 * v + 1, mid + 1, r, pos, val);
    t[v] = max(t[2 * v], t[2 * v + 1]);
}

int get_max (int v, int l, int r, int tl, int tr) {
    if (l > tr || r < tl) {
        return -1e18;
    }
    if (l >= tl && r <= tr) {
        return t[v];
    }
    int mid = (l + r) / 2;
    return max(get_max(2 * v, l, mid, tl, tr), get_max(2 * v + 1, mid + 1, r, tl, tr));
}

void solve(){
    int n;
    cin >> n;
    pii a[n + 7];
    for (int i = 1; i <= n; i++) {
        cin >> a[i].F >> a[i].S;
    }
    sort (a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        pref[i] = pref[i - 1] + a[i].S;
        upd (1, 1, n, i, pref[i] - a[i].F);
    }


    int ans = 0;
    for (int i = 1; i <= n; i++){
        int mx = get_max(1, 1, n, i, n);
        ans = max(ans, mx - pref[i - 1] + a[i].F);
//        cout << i << " " << mx << " " << ans << "\n";
    }

    cout << ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
        cout << "\n";
    }
}

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