Submission #565811

#TimeUsernameProblemLanguageResultExecution timeMemory
565811imtiyazrasool92Art Exhibition (JOI18_art)C++17
100 / 100
567 ms25248 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;


template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template < typename T_container, typename T = typename enable_if < !is_same<T_container, string>::value, typename T_container::value_type >::type > ostream & operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

void dbg_out() { cerr << '\n'; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef imtiyazrasool92
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

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];
        if (i + 1 < N)
            remove_prefix += (A[i + 1][0] - A[i][0]);

        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...