제출 #1303721

#제출 시각아이디문제언어결과실행 시간메모리
1303721khbaArt Exhibition (JOI18_art)C++20
100 / 100
227 ms12584 KiB
// 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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...