#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5000 + 3;
const ll INF = 1e18;
void build_edges(int pos1, int pos2, bool exact, vector<array<ll, 4>> &adj);
int n, a[N];
ll dist[N][N][2];
bool dp[N][N][2];
ll dijkstra(int pos1, int pos2, bool exact){
priority_queue<array<ll, 4>, vector<array<ll, 4>>, greater<array<ll, 4>>> pq;
for(int pos1 = 0; pos1 < n; ++pos1)
for(int pos2 = pos1; pos2 < n; ++pos2)
for(int exact = 0; exact <= 1; ++exact)
dist[pos1][pos2][exact] = INF;
dist[pos1][pos2][exact] = 0;
pq.push({0, pos1, pos2, exact});
vector<array<ll, 4>> adj;
while(!pq.empty()){
auto [d, pos1, pos2, exact] = pq.top();
pq.pop();
if(d != dist[pos1][pos2][exact]) continue;
if(pos1 == pos2) return d;
adj.clear();
build_edges(pos1, pos2, exact, adj);
for(auto [pos1_to, pos2_to, exact_to, cost]: adj){
ll cand = d + cost;
if(cand < dist[pos1_to][pos2_to][exact_to]){
dist[pos1_to][pos2_to][exact_to] = cand;
pq.push({cand, pos1_to, pos2_to, exact_to});
}
}
}
return INF;
}
void move_dp(int mv1, int mv2, int pos1, int pos2, bool exact, int x, vector<array<ll, 4>> &adj){
//cout << mv1 << " " << mv2 << " " << pos1 << " " << pos2 << " " << exact << " " << x << endl;
if(a[mv1] > x && x > a[mv2]) return;
if(a[mv1] < x && x < a[mv2]) return;
int new_x;
if(a[mv1] < x) new_x = max(a[mv1], a[mv2]);
else new_x = min(a[mv1], a[mv2]);
int new_exact = (a[mv1] == new_x) ? 0 : 1;
int new_pos1 = (a[mv1] == new_x) ? mv1 : pos1;
int new_pos2 = (a[mv2] == new_x) ? mv2 : pos2;
adj.push_back({new_pos1, new_pos2, new_exact, abs(x - new_x)});
//build_edges(new_pos1, new_pos2, new_exact);
//cout << pos1 << " " << pos2 << " " << exact << " -> " << new_pos1 << " " << new_pos2 << " " << new_exact << " " << abs(x - new_x) << endl;
}
void build_edges(int pos1, int pos2, bool exact, vector<array<ll, 4>> &adj){
if(pos1 == pos2) return;
auto &solved = dp[pos1][pos2][exact];
if(solved) return;
solved = true;
int x = !exact ? a[pos1] : a[pos2];
bool e1 = (x == a[pos1]), e2 = (x == a[pos2]);
vector<int> v1, v2;
if(e1){
v1.push_back(pos1 + 1);
if(pos1) v1.push_back(pos1 - 1);
}
else{
v1.push_back(pos1 + 1);
v1.push_back(pos1);
}
if(e2){
v2.push_back(pos2 - 1);
if(pos2 != n - 1) v2.push_back(pos2 + 1);
}
else{
v2.push_back(pos2 - 1);
v2.push_back(pos2);
}
move_dp(v1[0], v2[0], pos1, pos2, exact, x, adj);
if(v2.size() == 2) move_dp(v1[0], v2[1], pos1, pos2, exact, x, adj);
if(v1.size() == 2) move_dp(v1[1], v2[0], pos1, pos2, exact, x, adj);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for(int i = 0; i < n; ++i)
cin >> a[i];
vector<int> v;
v.push_back(a[0]);
for(int i = 1; i < n - 1; ++i){
if(v.back() <= a[i] && a[i] <= a[i + 1])
continue;
if(v.back() >= a[i] && a[i] >= a[i + 1])
continue;
v.push_back(a[i]);
}
v.push_back(a[n - 1]);
n = v.size();
for(int i = 0; i < n; ++i)
a[i] = v[i];
//build_edges(0, n - 1, 0);
ll ans = dijkstra(0, n - 1, 0);
if(ans == INF) cout << "NO\n";
else cout << ans << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
876 KB |
Output isn't correct |
| 2 |
Incorrect |
2 ms |
2284 KB |
Output isn't correct |
| 3 |
Incorrect |
7 ms |
12268 KB |
Output isn't correct |
| 4 |
Incorrect |
48 ms |
82924 KB |
Output isn't correct |
| 5 |
Incorrect |
124 ms |
215916 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
640 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
620 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
1260 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
876 KB |
Output isn't correct |
| 5 |
Incorrect |
2 ms |
3180 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1004 KB |
Output isn't correct |
| 2 |
Incorrect |
2 ms |
2668 KB |
Output isn't correct |
| 3 |
Incorrect |
8 ms |
12268 KB |
Output isn't correct |
| 4 |
Incorrect |
44 ms |
76268 KB |
Output isn't correct |
| 5 |
Incorrect |
43 ms |
75756 KB |
Output isn't correct |
| 6 |
Incorrect |
78 ms |
138348 KB |
Output isn't correct |
| 7 |
Incorrect |
78 ms |
130796 KB |
Output isn't correct |
| 8 |
Incorrect |
116 ms |
195436 KB |
Output isn't correct |
| 9 |
Incorrect |
115 ms |
199276 KB |
Output isn't correct |
| 10 |
Incorrect |
112 ms |
194796 KB |
Output isn't correct |
