Submission #46200

#	Time	Username	Problem	Language	Result	Execution time	Memory
46200		luciocf	Art Exhibition (JOI18_art)	C++14	0 / 100	2 ms	376 KiB

art

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 500010;

typedef long long ll;

struct D {
    ll menor, maior, s;
} dp[2][MAXN];

pair<ll, ll> num[MAXN];

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> num[i].first >> num[i].second;

    sort(num+1, num+n+1);

    dp[0][1].menor = 0LL, dp[0][1].maior = 0LL, dp[0][1].s = 0LL;
    dp[1][1].menor = num[1].first, dp[1][1].maior = num[1].first, dp[1][1].s = num[1].second;
    for (int i = 2; i <= n; i++)
    {
        if (dp[0][i-1].menor == 0)
        {
            if (dp[1][i-1].s-(dp[1][i-1].maior-dp[1][i-1].menor) < 0)
                dp[0][i] = dp[0][i-1];
            else
                dp[0][i] = dp[1][i-1];

            if (dp[1][i-1].s+num[i].second-(num[i].first-dp[1][i-1].menor) < num[i].second)
                dp[1][i].s = dp[1][i].menor = dp[1][i].maior = num[i].second;
            else
                dp[1][i].s = dp[1][i-1].s+num[i].second, dp[1][i].menor = dp[1][i-1].menor, dp[1][i].maior = dp[1][i-1].maior;
        }
        if (dp[0][i-1].s-(dp[0][i-1].maior-dp[0][i-1].menor) > dp[1][i-1].s-(dp[1][i-1].maior-dp[1][i-1].menor))
            dp[0][i] = dp[0][i-1];
        else
            dp[0][i] = dp[1][i-1];

        if (dp[0][i-1].s+num[i].second-(num[i].first-dp[0][i-1].menor) > dp[1][i-1].s+num[i].second-(num[i].first-dp[1][i-1].menor))
        {
            dp[1][i].menor = dp[0][i-1].menor;
            dp[1][i].maior = num[i].first;
            dp[1][i].s = dp[0][i-1].s+num[i].second;
        }
        else
        {
            dp[1][i].menor = dp[1][i-1].menor;
            dp[1][i].maior = num[i].first;
            dp[1][i].s = dp[1][i-1].s+num[i].second;
        }
    }
    if (dp[0][n].menor == 0 || (dp[1][n].s-(dp[1][n].maior-dp[1][n].menor) > dp[0][n].s-(dp[0][n].maior-dp[0][n].menor)))
        cout << dp[1][n].s-(dp[1][n].maior-dp[1][n].menor) << "\n";
    else
        cout << dp[0][n].s-(dp[0][n].maior-dp[0][n].menor) << "\n";
}

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