oj.uz

Submission #46200

# Submission time Handle Problem Language Result Execution time Memory
46200 2018-04-17T21:16:21 Z luciocf Art Exhibition (JOI18_art) C++14
0 / 100
 2 ms 376 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -