## 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 -