제출 #1321802

#제출 시각아이디문제언어결과실행 시간메모리
1321802bshaliArt Exhibition (JOI18_art)C++20
0 / 100
1 ms332 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define all(x) x.begin(), x.end()
#define inf (int)3e18
#define ff first
#define ss second
using vi = vector<int>;
using vii = vector<pair<int, int>>;
using vvi = vector<vector<int>>;
using pii = pair<int, int>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAX = 5e5 + 5;

array<int, 3> dp[MAX];
int a[MAX], b[MAX];

void solve()
{
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];

    dp[1][0] = b[1];
    dp[1][1] = a[1];
    dp[1][2] = a[1];
    for (int i = 2; i <= n; i++)
    {
        // If we dont take -> s
        // If we take -> sn
        int S = dp[i - 1][0] - dp[i - 1][1] + dp[i - 1][2];
        int Sn = dp[i - 1][0] + b[i] - max(dp[i - 1][1], a[i]) + min(dp[i - 1][2], a[i]);

        if (Sn > S)
        {
            dp[i][0] = dp[i - 1][0] + b[i];
            dp[i][1] = max(dp[i - 1][1], a[i]);
            dp[i][2] = min(dp[i - 1][2], a[i]);
        }
        else
        {
            dp[i] = dp[i - 1];
        }
    }

    // for (int i = 1; i <= n; i++)
    // {
    //     cout << dp[i][0] << ' ' << dp[i][1] << ' ' << dp[i][2] << '\n';
    // }

    cout << dp[n][0] - dp[n][1] + dp[n][2];
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int tt = 1;
    // cin >> tt;
    while (tt--)
        solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...