Submission #1321906

#TimeUsernameProblemLanguageResultExecution timeMemory
1321906ezimArt Exhibition (JOI18_art)C++20
100 / 100
145 ms28056 KiB
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 1e6, mod = 1e9 + 7, inf = 1e18;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> a(n);
    vector<ll> b(n);
    vector<pair<ll, ll>> p(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
        p[i] = {a[i], b[i]};
    }
    vector<ll> prefsum(n + 1, 0);
    sort(p.begin(), p.end());
    for (int i = 0; i < n; i++) {
        prefsum[i + 1] = prefsum[i] + p[i].second; 
    }
    vector<ll> v;
    vector<ll> prefm(n, 0);
    ll mxd = -1;
    ll e = prefsum[n] - (p[n - 1].first - p[0].first);
    for (int i = 0; i < n; i++) {
        v.push_back(p[i].first - p[0].first - prefsum[i]);
        mxd = max(mxd, v.back());
        prefm[i] = mxd;
    }
    ll ans = e;
    for (int i = n - 1; i >= 1; i--) {
        ll d = p[n - 1].first - p[i].first - (prefsum[n] - prefsum[i + 1]);
        ans = max(ans, p[i].second);
        ans = max(ans, e + prefm[i - 1] + d);
    }
    cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...