Submission #261804

#	Time	Username	Problem	Language	Result	Execution time	Memory
261804		tqbfjotld	Climbers (RMI18_climbers)	C++14	10 / 100	225 ms	401928 KiB

climbers

#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]!=-1) return memo[a][b][r];

    if (r && a+1==b) return 0;
    if (!r && a==b) return 0;
    if (r){
        memo[a][b][r] = INF;
        if (arr[a+1]==arr[b]) memo[a][b][r] = min(memo[a][b][r],dp(a+1,b,true));
        if (arr[b-1]<arr[b]){
            if (arr[b-1]>=min(arr[a+1],arr[a])){
                memo[a][b][r] = min(memo[a][b][r],dp(a,b-1,true)+arr[b]-arr[b-1]);
            }
            else if (true){
                memo[a][b][r] = min(memo[a][b][r],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])){
                memo[a][b][r] = min(memo[a][b][r],dp(a,b-1,true)+arr[b-1]-arr[b]);
            }
            else if (true){
                memo[a][b][r] = min(memo[a][b][r],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]){
                memo[a][b][r] = min(memo[a][b][r],dp(a+1,b-1,false)+arr[a+1]-arr[b]);
            }
            else if (b!=n-1 && arr[b+1]>=arr[a+1]){
                memo[a][b][r] = min(memo[a][b][r],dp(a+1,b,false)+arr[a+1]-arr[b]);
            }
        }
        else{
            if (arr[b-1]<=arr[a+1] && arr[b-1]<arr[b]){
                memo[a][b][r] = min(memo[a][b][r],dp(a+1,b-1,false)+arr[b]-arr[a+1]);
            }
            else if (b!=n-1 && arr[b+1]<=arr[a+1]){
                memo[a][b][r] = min(memo[a][b][r],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])){
            memo[a][b][r] = min(memo[a][b][r],dp(a,b+1,true)+abs(arr[b+1]-arr[b]));
        }
        //printf("%d %d right = %lld\n",a,b,memo[a][b][r]);
        return memo[a][b][r] = memo[a][b][r];
    }
    else{
        memo[a][b][r] = INF;
        if (arr[b]==arr[a]) memo[a][b][r] = min(memo[a][b][r],dp(a,b-1,false));
        if (arr[a+1]>arr[a]){
            if ( max(arr[b],arr[b+1])>=arr[a+1]){
                memo[a][b][r] = min(memo[a][b][r],dp(a+1,b,false)+arr[a+1]-arr[a]);
            }
            else if (true){
                memo[a][b][r] = min(memo[a][b][r],dp(a,b+1,true) + arr[b+1]-arr[a]);
            }
        }
        else if (min(arr[b],arr[b+1])<=arr[a+1]){
            memo[a][b][r] = min(memo[a][b][r],dp(a+1,b,false)+arr[a]-arr[a+1]);
        }
        else if (true){
            memo[a][b][r] = min(memo[a][b][r],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]){
                memo[a][b][r] = min(memo[a][b][r],dp(a,b,true)+arr[a]-arr[b]);
            }
            else if (a!=0 && arr[b]>=arr[a-1]){
                memo[a][b][r] = min(memo[a][b][r],dp(a-1,b,true)+arr[a]-arr[b]);
            }
            else{
            }
        }
        else{
            if (arr[a+1]>=arr[b]){
                memo[a][b][r] = min(memo[a][b][r],dp(a,b,true)+arr[b]-arr[a]);
            }
            else if (a!=0 && arr[a-1]>=arr[b]){
                memo[a][b][r] = min(memo[a][b][r],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])){
            memo[a][b][r] = min(memo[a][b][r],dp(a-1,b,false)+abs(arr[a-1]-arr[a]));
        }
        //printf("%d %d left = %lld\n",a,b,memo[a][b][r]);
        return memo[a][b][r] = memo[a][b][r];
    }
}


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 (stderr)

climbers.cpp: In function 'int main()':
climbers.cpp:101:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
climbers.cpp:104:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&t);
         ~~~~~^~~~~~~~~

• Subtask 1: 0 / 25
• Subtask 2: 5 / 25
• Subtask 3: 5 / 50