#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef array<int, 3> P;
const int N = 5050;
const ll INF = 1e18 + 10;
int n, a[N], p;
ll dp[2 * N][2 * N];
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= n; i++) {
int x; cin >> x;
if (p && a[p - 1] == x)
continue;
while (p >= 2 && (a[p - 2] < a[p - 1]) == (a[p - 1] < x))
--p;
a[p++] = x;
}
n = p;
for (int i = 0; i <= 2 * n - 2; i++)
for (int j = i; j <= 2 * n - 2; j++)
dp[i][j] = INF;
dp[0][2 * n - 2] = 0;
auto go = [&](int x, int y, int tx, int ty) {
int p = (x & 1) ? a[y / 2] : a[x / 2];
int nx = (x & 1) ? (tx ? x + 1 : x - 1) : (tx ? x + 2 : x - 2);
int ny = (y & 1) ? (ty ? y - 1 : y + 1) : (ty ? y - 2 : y + 2);
bool dx = (tx ? a[nx / 2 - 1] : a[nx / 2 + 1]) < a[nx / 2]; // true if climbing
bool dy = (ty ? a[ny / 2 + 1] : a[ny / 2 - 1]) < a[ny / 2];
if (dx != dy)
return P{ -1, -1, 0 };
if (a[nx / 2] == a[ny / 2])
return P{ nx, ny, abs(a[nx / 2] - p) };
if (dx == (a[nx / 2] < a[ny / 2]))
return P{ nx, ty ? ny + 1 : ny - 1, abs(a[nx / 2] - p) };
else
return P{ tx ? nx - 1 : nx + 1, ny, abs(a[ny / 2] - p) };
};
for (int d = 2 * n - 2; d >= 1; d--) {
for (int l = 0; l + d < 2 * n - 2; l++) {
int r = l + d;
auto [x, y, d] = go(l, r, 1, 0); // only alice goes forward
if (x != -1)
dp[x][y] = min(dp[x][y], dp[l][r] + d);
}
for (int r = 2 * n - 2; r - d > 0; r--) {
int l = r - d;
auto [x, y, d] = go(l, r, 0, 1); // only bob goes forward
if (x != -1)
dp[x][y] = min(dp[x][y], dp[l][r] + d);
}
for (int l = 0; l + d <= 2 * n - 2; l++) {
int r = l + d;
if (r != 2 * n - 2) {
auto [x, y, d] = go(l, r, 1, 0); // only alice goes forward
if (x != -1)
dp[x][y] = min(dp[x][y], dp[l][r] + d);
}
if (l != 0) {
auto [x, y, d] = go(l, r, 0, 1); // only bob goes forward
if (x != -1)
dp[x][y] = min(dp[x][y], dp[l][r] + d);
}
auto [x, y, d] = go(l, r, 1, 1); // alice, bob goes forward
if (x != -1)
dp[x][y] = min(dp[x][y], dp[l][r] + d);
}
}
ll ans = INF;
for (int i = 0; i < n; i++)
ans = min(ans, dp[2 * i][2 * i]);
cout << ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
1236 KB |
Output isn't correct |
| 2 |
Incorrect |
7 ms |
4180 KB |
Output isn't correct |
| 3 |
Incorrect |
80 ms |
24124 KB |
Output isn't correct |
| 4 |
Execution timed out |
1008 ms |
165456 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1090 ms |
431564 KB |
Time limit exceeded |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
724 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
1876 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 5 |
Incorrect |
13 ms |
5844 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
1108 KB |
Output isn't correct |
| 2 |
Incorrect |
6 ms |
3796 KB |
Output isn't correct |
| 3 |
Incorrect |
67 ms |
22532 KB |
Output isn't correct |
| 4 |
Execution timed out |
840 ms |
152140 KB |
Time limit exceeded |
| 5 |
Execution timed out |
850 ms |
151004 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1108 ms |
275732 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1094 ms |
260580 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1114 ms |
390476 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1112 ms |
397756 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1115 ms |
388988 KB |
Time limit exceeded |
