Submission #1270636

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270636		flaming_top1	Art Exhibition (JOI18_art)	C++20	100 / 100	136 ms	19956 KiB

art

#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;
}

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