Submission #128233

#	Time	Username	Problem	Language	Result	Execution time	Memory
128233		wasyl	Art Exhibition (JOI18_art)	C++11	100 / 100	319 ms	21036 KiB

art

#include <bits/stdc++.h>
#define st first
#define nd second
using namespace std;
using ll = long long;

constexpr int nax = 5e5;
constexpr ll inf = 1e18;

int n;
pair< ll, int > pat[nax + 1];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 1; i <= n; ++i)
        cin >> pat[i].st >> pat[i].nd;

    sort(begin(pat) + 1, begin(pat) + 1 + n);

    ll mi = inf;
    ll su = 0;
    ll res = -inf;

    for (int i = 0; i <= n; ++i)
    {
        su += pat[i].nd;
        res = max(res, -pat[i].st + su - mi);
        if (i + 1 <= n)
            mi = min(mi, su - pat[i + 1].st);
        //cerr << i << ' ' << res << '\n';
    }

    cout << res << '\n';
}

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