oj.uz

답안 #46202

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
46202 2018-04-18T00:22:01 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;

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, 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++)
    {
        ll aux = menor[0][i-1];
        if (menor[0][i-1] == 0LL) aux = num[i].first;
        if (s[0][i-1]-(num[i].first-aux) > s[1][i-1]-(num[i].first-menor[1][i-1]))
        {
            dp[1][i] = s[0][i-1]+num[i].second-(num[i].first-aux);
            s[1][i] = s[0][i-1]+num[i].second;
            menor[1][i] = aux;
        }
        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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -