Submission #157181

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

game

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

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