oj.uz

Submission #156893

# Submission time Handle Problem Language Result Execution time Memory
156893 2019-10-08T06:55:45 Z undecember 막대기 (KOI13_game) C++17
62 / 100
 1000 ms 4708 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef double ll;

int _N, _L;
vector<pii> u2d, d2u;
vector<ll> dpmu, dpmd;

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

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));
        d2u.push_back(pii(b, a));
    }
    sort(u2d.begin(), u2d.end());
    sort(d2u.begin(), d2u.end());

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

    ll mx = 0;
    for (i = 0; i < _N; i++) mx = max(mx, dpu(i));
    for (i = 0; i < _N; i++) mx = max(mx, dpd(i));

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

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

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

    int fr = lower_bound(d2u.begin(), d2u.end(), pii(u2d[index].second, 0)) - d2u.begin();
    int to = lower_bound(d2u.begin(), d2u.end(), pii(u2d[index].second, u2d[index].first)) - d2u.begin();

    for (int i = fr; i < to; i++) ret = max(ret, mn + dpd(i));

    return dpmu[index] = ret;
}

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

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

    int fr = lower_bound(u2d.begin(), u2d.end(), pii(d2u[index].second, 0)) - u2d.begin();
    int to = lower_bound(u2d.begin(), u2d.end(), pii(d2u[index].second, d2u[index].first)) - u2d.begin();

    for (int i = fr; i < to; i++) ret = max(ret, mn + dpu(i));

    return dpmd[index] = ret;
}

Compilation message

game.cpp: In function 'int main()':
game.cpp:17: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:23: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 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 256 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 64 ms 2724 KB Output is correct
2 Correct 92 ms 2540 KB Output is correct
3 Correct 146 ms 4592 KB Output is correct
4 Correct 222 ms 4580 KB Output is correct
5 Correct 180 ms 4708 KB Output is correct

Subtask #3
16.0 / 16.0

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

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 380 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 12 ms 1016 KB Output is correct
2 Correct 12 ms 916 KB Output is correct
3 Execution timed out 1071 ms 3052 KB Time limit exceeded
4 Halted 0 ms 0 KB -