Submission #1303721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303721		khba	Art Exhibition (JOI18_art)	C++20	100 / 100	227 ms	12584 KiB

art

// author: khba
// road to IZhO gold

#include <bits/stdc++.h>
using namespace std;
#define int long long

// #ifdef khba
// // #include "save.h"
// #else
// #define print(...) 42
// #endif

void t_main() {
    int n, ans = 0; cin >> n;
    vector <int> a(n), b(n);
    for (int i = 0; i < n; ++i) cin >> a[i] >> b[i];
    vector <int> o(n);
    iota(begin(o), end(o), 0);
    sort(begin(o), end(o), [&] (int r, int l) { return a[r] < a[l]; });
    int mx = a[o.front()], s = 0;
    for (int i : o) {
        mx = max(mx, a[i] - s);
        s += b[i];
        ans = max(ans, -a[i] + mx + s);
        // s - a_max + a_min
        // -a_max + pref[max] + a_min - pref[min-1]
    }
    cout << ans;
}

int32_t main()
{
#ifdef khba
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int32_t t = 1;
    // cin >> t;
    while (t--) { t_main(); cout << "\n"; }
    return 0;
}

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