Submission #197619

#TimeUsernameProblemLanguageResultExecution timeMemory
197619joylintpArt Exhibition (JOI18_art)C++17
100 / 100
270 ms28864 KiB
#include<bits/stdc++.h>
#define int long long

using namespace std;

int n, mn[500001], mx[500001], ans;
pair<int, int> v[500001] = {};

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> v[i].first >> v[i].second;
    sort(v, v + n + 1);

    for (int i = 1; i <= n; i++)
        v[i].second += v[i - 1].second;

    mn[1] = v[0].second - v[1].first;
    for (int i = 2; i <= n; i++)
        mn[i] = min(mn[i - 1], v[i - 1].second - v[i].first);
    mx[n] = v[n].second - v[n].first;
    for (int i = n - 1; i >= 1; i--)
        mx[i] = max(mx[i + 1], v[i].second - v[i].first);

    for (int i = 1; i <= n; i++)
        ans = max(ans, mx[i] - mn[i]);
    cout << ans << '\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...