Submission #565803

#TimeUsernameProblemLanguageResultExecution timeMemory
565803imtiyazrasool92Art Exhibition (JOI18_art)C++17
0 / 100
0 ms212 KiB
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>

using namespace std;

int main() {
    int N;
    cin >> N;

    vector<array<int64_t, 2>> A(N);
    for (auto &[x, y] : A)
        cin >> x >> y;

    sort(A.begin(), A.end());

    priority_queue<int64_t> Q;
    Q.push((A[1][0] - A[0][0]) - A[0][1]);

    int64_t answer = A[0][1];
    int64_t prefix = A[0][1];
    int64_t remove_prefix = (A[1][0] - A[0][0]) - A[0][1];

    for (int i = 1; i < N; i++) {
        prefix += A[i][1];
        prefix -= abs(A[i][0] - A[i - 1][0]);

        answer = max<int64_t>(answer, prefix);
        answer = max<int64_t>(answer, prefix + Q.top());

        remove_prefix -= A[i][1];
        remove_prefix += (A[i][1] - A[i - 1][1]);

        Q.push(remove_prefix);
    }

    cout << answer;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...