제출 #556899

#제출 시각아이디문제언어결과실행 시간메모리
556899alextodoranArt Exhibition (JOI18_art)C++17
100 / 100
218 ms20780 KiB
/**
 ____ ____ ____ ____ ____
||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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...