Submission #556899

#	Time	Username	Problem	Language	Result	Execution time	Memory
556899		alextodoran	Art Exhibition (JOI18_art)	C++17	100 / 100	218 ms	20780 KiB

art

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 500000;

struct Artwork {
    ll dim, val;
};
bool operator < (const Artwork &a, const Artwork &b) {
    return a.dim < b.dim;
}

int N;
Artwork art[N_MAX + 2];

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

    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> art[i].dim >> art[i].val;
    }
    sort(art + 1, art + N + 1);

    ll answer = 0;
    ll pref = 0;
    ll mx = LLONG_MIN / 2;
    for (int i = 1; i <= N; i++) {
        mx = max(mx, art[i].dim - pref);
        pref += art[i].val;
        answer = max(answer, pref - art[i].dim + mx);
    }
    cout << answer << "\n";

    return 0;
}

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