#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
constexpr int NMAX = 5005;
constexpr LL INF = 1LL * 1e18;
typedef pair <LL, pair <int, int> > PLLII;
int N;
LL dp[NMAX][NMAX];
int V[NMAX];
LL modul (LL x) {
if (x < 0) x = -x;
return x;
}
void Read () {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
for (int i = 1; i <= N; ++ i )
cin >> V[i];
vector <int> aux;
aux.push_back(V[1]);
for (int i = 2; i < N; ++ i ) {
if (V[i-1] <= V[i] && V[i] <= V[i+1]) continue;
if (V[i-1] >= V[i] && V[i] >= V[i+1]) continue;
aux.push_back(V[i]);
}
aux.push_back(V[N]);
for (int i = aux.size()+1; i <= N; ++ i )
V[i] = 0;
N = aux.size();
for (int i = 1; i <= N; ++ i )
V[i] = aux[i-1];
}
priority_queue< PLLII, vector<PLLII>, greater<PLLII> > H;
bool Good (int varf, int drum) {
if (V[drum] < V[drum+1])
return (V[drum] <= V[varf] && V[varf] <= V[drum+1]);
else
return (V[drum] >= V[varf] && V[varf] >= V[drum+1]);
}
void PushBack (int A, int B, LL val) {
if (val < dp[A][B]) {
dp[A][B] = val;
H.push({val, {A, B}});
}
}
void Solve () {
for (int i = 1; i <= N; ++ i )
for (int j = 1; j <= N; ++ j )
dp[i][j] = INF;
dp[1][N-1] = 0;
H.push({0, {1, N-1}});
while (!H.empty()) {
PLLII x = H.top();
H.pop();
if (x.second.first == x.second.second || x.second.first == x.second.second + 1) {
cout << x.first << '\n';
return;
}
if (x.first != dp[x.second.first][x.second.second]) continue;
int vf = x.second.first;
int dr = x.second.second;
LL cost = x.first;
if (vf < N && Good(vf + 1, dr))
PushBack(vf+1, dr, cost + modul(V[vf+1] - V[vf]));
if (vf > 1 && Good(vf - 1, dr))
PushBack(vf-1, dr, cost + modul(V[vf] - V[vf-1]));
if (Good(dr, vf))
PushBack(dr, vf, cost + modul(V[vf] - V[dr]));
if (vf > 1 && Good(dr, vf-1))
PushBack(dr, vf-1, cost + modul(V[vf] - V[dr]));
if (Good(dr+1, vf))
PushBack(dr+1, vf, cost + modul(V[vf] - V[dr+1]));
if (vf > 1 && Good(dr+1, vf-1))
PushBack(dr+1, vf-1, cost + modul(V[vf] - V[dr+1]));
}
cout << -1 << '\n';
}
int main () {
Read();
Solve();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
716 KB |
Output is correct |
2 |
Correct |
1 ms |
2124 KB |
Output is correct |
3 |
Correct |
7 ms |
12108 KB |
Output is correct |
4 |
Correct |
38 ms |
82736 KB |
Output is correct |
5 |
Correct |
97 ms |
196228 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
460 KB |
Output is correct |
3 |
Correct |
1 ms |
972 KB |
Output is correct |
4 |
Correct |
1 ms |
716 KB |
Output is correct |
5 |
Correct |
2 ms |
3020 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
716 KB |
Output is correct |
2 |
Correct |
1 ms |
1996 KB |
Output is correct |
3 |
Correct |
64 ms |
11388 KB |
Output is correct |
4 |
Correct |
125 ms |
75952 KB |
Output is correct |
5 |
Correct |
162 ms |
75492 KB |
Output is correct |
6 |
Correct |
176 ms |
137704 KB |
Output is correct |
7 |
Correct |
185 ms |
130212 KB |
Output is correct |
8 |
Correct |
173 ms |
186060 KB |
Output is correct |
9 |
Correct |
216 ms |
187844 KB |
Output is correct |
10 |
Correct |
208 ms |
185532 KB |
Output is correct |