Submission #156893

#	Time	Username	Problem	Language	Result	Execution time	Memory
156893		undecember	막대기 (KOI13_game)	C++17	62 / 100	1071 ms	4708 KiB

game

#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 (stderr)

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 / 11
• Subtask 2: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 22 / 22
• Subtask 5: 0 / 38