#include <bits/stdc++.h>
#define DIM 5010
#define INF 2000000000
using namespace std;
priority_queue <pair<int,pair<int,int> >, vector<pair<int,pair<int,int> > >, greater<pair<int,pair<int,int> > > > h;
int dp[DIM][DIM],v[DIM];
int n,i,j;
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>n;
for (i=1;i<=n;i++)
cin>>v[i];
int k = 1;
for (i=2;i<n;i++){
if ( (v[i] > v[i-1] && v[i] > v[i+1]) || (v[i] < v[i-1] && v[i] < v[i+1]))
v[++k] = v[i];
}
v[++k] = 0;
n = k;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
dp[i][j] = INF;
/// dp[capat][segment] - A/B se afla intr un capat de segm si celalalt e pe un segm
dp[1][n-1] = 0;
h.push(make_pair(0,make_pair(1,n-1)));
while (!h.empty()){
int cost = h.top().first;
int capat = h.top().second.first;
int segm = h.top().second.second;
h.pop();
if (capat == segm || capat == segm+1){ /// au ajuns in acelasi punct
cout<<cost;
return 0;
}
if (capat < segm){ /// A e in capat
if (v[capat] < v[capat+1]){ /// trebuie sa urc
if (v[segm] > v[segm+1]){ /// poate si B sa urce
if (v[capat+1] <= v[segm]){
int val = v[capat+1] - v[capat];
if (dp[capat][segm] + val < dp[capat+1][segm]){
dp[capat+1][segm] = dp[capat][segm] + val;
h.push(make_pair(dp[capat+1][segm],make_pair(capat+1,segm)));
}
} else {
int val = v[segm] - v[capat];
if (dp[capat][segm] + val < dp[segm][capat]){
dp[segm][capat] = dp[capat][segm] + val;
h.push(make_pair(dp[segm][capat],make_pair(segm,capat)));
}
}
} else { /// B trebuie sa se intoarca inapoi
if (v[capat+1] <= v[segm+1]){
int val = v[capat+1] - v[capat];
if (dp[capat][segm] + val < dp[capat+1][segm]){
dp[capat+1][segm] = dp[capat][segm] + val;
h.push(make_pair(dp[capat+1][segm],make_pair(capat+1,segm)));
}
} else {
int val = v[segm+1] - v[capat];
if (dp[capat][segm] + val < dp[segm+1][capat]){
dp[segm+1][capat] = dp[capat][segm] + val;
h.push(make_pair(dp[segm+1][capat],make_pair(segm+1,capat)));
}
}
}
} else { /// A coboara
if (v[segm] > v[segm+1]){ /// trb sa coboare si B, dar se duce inapoi
if (v[capat+1] >= v[segm+1]){
int val = v[capat] - v[capat+1];
if (dp[capat][segm] + val < dp[capat+1][segm]){
dp[capat+1][segm] = dp[capat][segm] + val;
h.push(make_pair(dp[capat+1][segm],make_pair(capat+1,segm)));
}
} else {
int val = v[capat] - v[segm+1];
if (dp[capat][segm] + val < dp[segm+1][capat]){
dp[segm+1][capat] = dp[capat][segm] + val;
h.push(make_pair(dp[segm+1][capat],make_pair(segm+1,capat)));
}
}
} else { /// coboara B, merge inainte
if (v[capat+1] >= v[segm]){
int val = v[capat] - v[capat+1];
if (dp[capat][segm] + val < dp[capat+1][segm]){
dp[capat+1][segm] = dp[capat][segm] + val;
h.push(make_pair(dp[capat+1][segm],make_pair(capat+1,segm)));
}
} else {
int val = v[capat] - v[segm];
if (dp[capat][segm] + val < dp[segm][capat]){
dp[segm][capat] = dp[capat][segm] + val;
h.push(make_pair(dp[segm][capat],make_pair(segm,capat)));
}
}
}
}
} else { /// B e in capat
if (v[capat] < v[capat-1]){ /// B urca
if (v[segm+1] > v[segm]){ /// poate si A sa urce
if (v[segm+1] >= v[capat-1]){
int val = v[capat-1] - v[capat];
if (dp[capat][segm] + val < dp[capat-1][segm]){
dp[capat-1][segm] = dp[capat][segm] + val;
h.push(make_pair(dp[capat-1][segm],make_pair(capat-1,segm)));
}
} else {
int val = v[segm+1] - v[capat];
if (dp[capat][segm] + val < dp[segm+1][capat-1]){
dp[segm+1][capat-1] = dp[capat][segm] + val;
h.push(make_pair(dp[segm+1][capat-1],make_pair(segm+1,capat-1)));
}
}
} else { /// A urca, dar se intoarce inapoi
if (v[segm-1] >= v[capat-1]){
int val = v[capat-1] - v[capat];
if (dp[capat][segm] + val < dp[capat-1][segm]){
dp[capat-1][segm] = dp[capat][segm] + val;
h.push(make_pair(dp[capat-1][segm],make_pair(capat-1,segm)));
}
} else {
int val = v[segm] - v[capat];
if (dp[capat][segm] + val < dp[segm][capat-1]){
dp[segm][capat-1] = dp[capat][segm] + val;
h.push(make_pair(dp[segm][capat-1],make_pair(segm,capat-1)));
}
}
}
} else { /// B coboara
if (v[segm] < v[segm+1]){ /// A cobora, dar se intoarce inapoi
if (v[segm] <= v[capat-1]){
int val = v[capat] - v[capat-1];
if (dp[capat][segm] + val < dp[capat-1][segm]){
dp[capat-1][segm] = dp[capat][segm] + val;
h.push(make_pair(dp[capat-1][segm],make_pair(capat-1,segm)));
}
} else {
int val = v[capat] - v[segm];
if (dp[capat][segm] + val < dp[segm][capat-1]){
dp[segm][capat-1] = dp[capat][segm] + val;
h.push(make_pair(dp[segm][capat-1],make_pair(segm,capat-1)));
}
}
} else { /// A coboara, merge inainte
if (v[segm+1] <= v[capat-1]){
int val = v[capat] - v[capat-1];
if (dp[capat][segm] + val < dp[capat-1][segm]){
dp[capat-1][segm] = dp[capat][segm] + val;
h.push(make_pair(dp[capat-1][segm],make_pair(capat-1,segm)));
}
} else {
int val = v[capat] - v[segm+1];
if (dp[capat][segm] + val < dp[segm+1][capat-1]){
dp[segm+1][capat-1] = dp[capat][segm] + val;
h.push(make_pair(dp[segm+1][capat-1],make_pair(segm+1,capat-1)));
}
}
}
}
}
}
cout<<"NO";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
676 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
1740 KB |
Output isn't correct |
| 3 |
Incorrect |
5 ms |
8140 KB |
Output isn't correct |
| 4 |
Incorrect |
30 ms |
47436 KB |
Output isn't correct |
| 5 |
Incorrect |
61 ms |
98292 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
972 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
716 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
2476 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
588 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
1740 KB |
Output isn't correct |
| 3 |
Incorrect |
5 ms |
7628 KB |
Output isn't correct |
| 4 |
Incorrect |
24 ms |
43764 KB |
Output isn't correct |
| 5 |
Incorrect |
28 ms |
43480 KB |
Output isn't correct |
| 6 |
Incorrect |
42 ms |
76824 KB |
Output isn't correct |
| 7 |
Incorrect |
50 ms |
72828 KB |
Output isn't correct |
| 8 |
Incorrect |
60 ms |
93248 KB |
Output isn't correct |
| 9 |
Incorrect |
55 ms |
94064 KB |
Output isn't correct |
| 10 |
Incorrect |
54 ms |
93124 KB |
Output isn't correct |
