Submission #565806

#	Time	Username	Problem	Language	Result	Execution time	Memory
565806		imtiyazrasool92	Art Exhibition (JOI18_art)	C++17	0 / 100	0 ms	212 KiB

art

#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][0] - A[i - 1][0]);

        Q.push(remove_prefix);
    }

    cout << answer;
}

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