#include <bits/stdc++.h>
using namespace std;
#define INF 999999999999999999LL
int arr[5005];
long long memo[5005][5005][2];
int n;
long long dp(int a, int b, bool r){
if (memo[a][b][r]==-2) return INF;
if (memo[a][b][r]!=-1) return memo[a][b][r];
if (r && a+1==b) return 0;
if (!r && a==b) return 0;
memo[a][b][r] = -2;
if (r){
long long ans = INF;
if (arr[a+1]==arr[b]) ans = min(ans,dp(a+1,b,true));
if (arr[b-1]<arr[b]){
if (arr[b-1]>=min(arr[a+1],arr[a])){
ans = min(ans,dp(a,b-1,true)+arr[b]-arr[b-1]);
}
else if (arr[a+1]>arr[a]){
ans = min(ans,dp(a,b-1,false)+arr[b]-arr[a]);
}
}
if (arr[b-1]>arr[b]){
if (arr[b-1]<=max(arr[a],arr[a+1])){
ans = min(ans,dp(a,b-1,true)+arr[b-1]-arr[b]);
}
else if (arr[a+1]<arr[a]){
ans = min(ans,dp(a,b-1,false)+arr[a]-arr[b]);
}
}
if (arr[a+1]>arr[a]){
if (arr[b-1]>=arr[a+1] && arr[b-1]>arr[b]){
ans = min(ans,dp(a+1,b-1,false)+arr[a+1]-arr[b]);
}
else if (b!=n-1 && arr[b+1]>=arr[a+1]){
ans = min(ans,dp(a+1,b,false)+arr[a+1]-arr[b]);
}
}
else{
if (arr[b-1]<=arr[a+1] && arr[b-1]<arr[b]){
ans = min(ans,dp(a+1,b-1,false)+arr[b]-arr[a+1]);
}
else if (b!=n-1 && arr[b+1]<=arr[a+1]){
ans = min(ans,dp(a+1,b,false)+arr[b]-arr[a+1]);
}
}
if (b!=n-1 && arr[b+1]>=min(arr[a],arr[a+1]) && arr[b+1]<=max(arr[a],arr[a+1])){
ans = min(ans,dp(a,b+1,true)+abs(arr[b+1]-arr[b]));
}
//printf("%d %d right = %lld\n",a,b,ans);
return memo[a][b][r] = ans;
}
else{
long long ans = INF;
if (arr[b]==arr[a]) ans = min(ans,dp(a,b-1,false));
if (arr[a+1]>arr[a]){
if ( max(arr[b],arr[b+1])>=arr[a+1]){
ans = min(ans,dp(a+1,b,false)+arr[a+1]-arr[a]);
}
else if (arr[b+1]>arr[b]){
ans = min(ans,dp(a,b+1,true) + arr[b+1]-arr[a]);
}
}
else if (min(arr[b],arr[b+1])<=arr[a+1]){
ans = min(ans,dp(a+1,b,false)+arr[a]-arr[a+1]);
}
else if (arr[b+1]<arr[b]){
ans = min(ans,dp(a,b+1,true)+arr[a]-arr[b+1]);
}
if (arr[b]<arr[b+1]){
if (arr[a+1]<=arr[b] && arr[a+1]<arr[a]){
ans = min(ans,dp(a,b,true)+arr[a]-arr[b]);
}
else if (a!=0 && arr[b]>=arr[a-1]){
ans = min(ans,dp(a-1,b,true)+arr[a]-arr[b]);
}
else{
}
}
else{
if (arr[a+1]>=arr[b]){
ans = min(ans,dp(a,b,true)+arr[b]-arr[a]);
}
else if (a!=0 && arr[a-1]>=arr[b]){
ans = min(ans,dp(a-1,b,true)+arr[b]-arr[a]);
}
}
if (a!=0 && arr[a-1]>=min(arr[b],arr[b+1]) && arr[a-1]<=max(arr[b],arr[b+1])){
ans = min(ans,dp(a-1,b,false)+abs(arr[a-1]-arr[a]));
}
//printf("%d %d left = %lld\n",a,b,ans);
return memo[a][b][r] = ans;
}
}
int main(){
memset(memo,-1,sizeof(memo));
scanf("%d",&n);
for (int x = 0; x<n; x++){
int t;
scanf("%d",&t);
if (x>=2){
if (t>=arr[x-1] && arr[x-1]>=arr[x-2]){
arr[x-1] = t;
x--;
n--;
continue;
}
else if (t<=arr[x-1] && arr[x-1]<=arr[x-2]){
arr[x-1] = t;
x--;n--;
continue;
}
}
arr[x] = t;
}
for (int x = 0; x<n; x++){
//printf("arr %d\n",arr[x]);
}
long long res = min(dp(0,n-2,false),dp(0,n-1,true));
if (res==INF){
printf("NO");
}
else
printf("%lld",res);
}
Compilation message
climbers.cpp: In function 'int main()':
climbers.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
climbers.cpp:106:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&t);
~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
210 ms |
392440 KB |
Output isn't correct |
| 2 |
Incorrect |
230 ms |
392440 KB |
Output isn't correct |
| 3 |
Incorrect |
216 ms |
392568 KB |
Output isn't correct |
| 4 |
Incorrect |
212 ms |
392516 KB |
Output isn't correct |
| 5 |
Incorrect |
208 ms |
392568 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
210 ms |
392440 KB |
Output isn't correct |
| 2 |
Incorrect |
208 ms |
392440 KB |
Output isn't correct |
| 3 |
Incorrect |
209 ms |
392464 KB |
Output isn't correct |
| 4 |
Incorrect |
221 ms |
392696 KB |
Output isn't correct |
| 5 |
Incorrect |
214 ms |
392440 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
209 ms |
392540 KB |
Output is correct |
| 2 |
Incorrect |
211 ms |
392696 KB |
Output isn't correct |
| 3 |
Incorrect |
234 ms |
403960 KB |
Output isn't correct |
| 4 |
Incorrect |
211 ms |
392568 KB |
Output isn't correct |
| 5 |
Incorrect |
211 ms |
392568 KB |
Output isn't correct |
| 6 |
Incorrect |
209 ms |
392556 KB |
Output isn't correct |
| 7 |
Incorrect |
223 ms |
392952 KB |
Output isn't correct |
| 8 |
Incorrect |
210 ms |
392644 KB |
Output isn't correct |
| 9 |
Incorrect |
235 ms |
392560 KB |
Output isn't correct |
| 10 |
Incorrect |
217 ms |
392828 KB |
Output isn't correct |
