제출 #46201

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
46201		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;

pair<ll, ll> num[MAXN];
ll dp[2][MAXN], s[2][MAXN], menor[2][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[1][1] = num[1].second-num[1].first, s[1][1] = num[1].second, menor[1][1] = num[1].first;
    dp[0][1] = 0LL, s[0][1] = 0LL, menor[0][1] = 0LL;

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

        if (dp[0][i-1] > dp[1][i-1])
        {
            dp[0][i] = dp[0][i-1];
            s[0][i] = s[0][i-1];
            menor[0][i] = menor[0][i-1];
        }
        else
        {
            dp[0][i] = dp[1][i-1];
            s[0][i] = s[1][i-1];
            menor[0][i] = menor[1][i-1];
        }
    }
    if (menor[0][n] == 0LL)
        cout << dp[1][n] << "\n";
    else
        cout << max(dp[0][n], dp[1][n]) << "\n";
}

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