oj.uz

Submission #157180

# Submission time Handle Problem Language Result Execution time Memory
157180 2019-10-10T02:33:04 Z undecember 막대기 (KOI13_game) C++17
62 / 100
 1000 ms 4972 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef double ll;
int _N, _L;
vector<int> recu, recd;
vector<pii> _U2D, _D2U;
vector<vector<int>> u2d, d2u;
vector<ll> dpmu, dpmd;

ll dpu(int index);
ll dpd(int index);

bool cmp(pii a, pii b) {return a.second != b.second ? a.second < b.second : a.first < b.first;}
void remap();

int main(void)
{
    scanf("%d%d", &_N, &_L);

    int i;
    for (i = 0; i < _N; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        _U2D.push_back(pii(a, b));
    }
    remap();

    u2d.assign(recu.size(), vector<int>());
    d2u.assign(recd.size(), vector<int>());
    for (i = 0; i < _N; i++)
    {
        u2d[_U2D[i].first].push_back(i);
        d2u[_U2D[i].second].push_back(i);
    }

    dpmu.assign(_N, 0);
    dpmd.assign(_N, 0);

    ll mx = 0;
    for (i = _N - 1; i >= 0; i--) mx = max(mx, dpu(i));
    for (i = _N - 1; i >= 0; i--) mx = max(mx, dpd(i));

    printf("%lld", (long long)mx);
    return 0;
}

void remap()
{
    int i;

    sort(_U2D.begin(), _U2D.end());
    for (i = 0; i < _N; i++)
    {
        bool fl = recu.size() == 0;
        if (!fl) fl = recu[recu.size() - 1] != _U2D[i].first;
        if (fl) recu.push_back(_U2D[i].first);

        _U2D[i].first = recu.size() - 1;
    }

    sort(_U2D.begin(), _U2D.end(), cmp);
    for (i = 0; i < _N; i++)
    {
        bool fl = recd.size() == 0;
        if (!fl) fl = recd[recd.size() - 1] != _U2D[i].second;
        if (fl) recd.push_back(_U2D[i].second);

        _U2D[i].second = recd.size() - 1;
    }

    sort(_U2D.begin(), _U2D.end());
}

ll dpu(int index)
{
    if (dpmu[index] != 0) return dpmu[index];

    ll ret = recu[_U2D[index].first] - recd[_U2D[index].second];
    ret = abs(ret) + _L;
    ll mn = ret;

    for (auto it : d2u[_U2D[index].second])
    {
        if (_U2D[it].first >= _U2D[index].first) break;
        ret = max(ret, dpd(it) + mn);
    }

    return dpmu[index] = ret;
}

ll dpd(int index)
{
    if (dpmd[index] != 0) return dpmd[index];

    ll ret = recu[_U2D[index].first] - recd[_U2D[index].second];
    ret = abs(ret) + _L;
    ll mn = ret;

    for (auto it : u2d[_U2D[index].first])
    {
        if (_U2D[it].second >= _U2D[index].second) break;
        ret = max(ret, dpu(it) + mn);
    }

    return dpmd[index] = ret;
}

Compilation message

game.cpp: In function 'int main()':
game.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &_N, &_L);
     ~~~~~^~~~~~~~~~~~~~~~~~
game.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 2672 KB Output is correct
2 Correct 89 ms 2672 KB Output is correct
3 Correct 131 ms 4832 KB Output is correct
4 Correct 220 ms 4752 KB Output is correct
5 Correct 173 ms 4972 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 356 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct

Subtask #5
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1144 KB Output is correct
2 Correct 11 ms 1272 KB Output is correct
3 Execution timed out 1072 ms 4376 KB Time limit exceeded
4 Halted 0 ms 0 KB -