Submission #1270636

#TimeUsernameProblemLanguageResultExecution timeMemory
1270636flaming_top1Art Exhibition (JOI18_art)C++20
100 / 100
136 ms19956 KiB
#include <bits/stdc++.h>
using namespace std;

#define SPED                                                                                                           \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);
#define endl "\n"
#define lint long long

int main()
{
    SPED;
    int N;
    cin >> N;
    vector<pair<lint, lint>> v(N);
    for (int i = 0; i < N; ++i)
        cin >> v[i].first >> v[i].second; // A_i, B_i

    sort(v.begin(), v.end()); // sort by A

    vector<lint> A(N + 1), C(N + 1), P(N + 1, 0);
    for (int i = 1; i <= N; ++i)
    {
        A[i] = v[i - 1].first;
        C[i] = max<lint>(0, v[i - 1].second);
        P[i] = P[i - 1] + C[i];
    }

    lint ans = LLONG_MIN;
    lint mn = LLONG_MAX; // mn = min_{1..r}( P_{l-1} - A_l )

    for (int r = 1; r <= N; ++r)
    {
        // cập nhật mn với l = r (sẵn sàng dùng cho r hiện tại và các r sau)
        mn = min(mn, P[r - 1] - A[r]);
        // dp[r] = (P_r - A_r) - mn
        lint cur = (P[r] - A[r]) - mn;
        ans = max(ans, cur);
    }

    cout << ans << endl;
    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...