Submission #197619

#	Time	Username	Problem	Language	Result	Execution time	Memory
197619		joylintp	Art Exhibition (JOI18_art)	C++17	100 / 100	270 ms	28864 KiB

art

#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;
}

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