Submission #261692

#	Time	Username	Problem	Language	Result	Execution time	Memory
261692		tqbfjotld	Climbers (RMI18_climbers)	C++14	5 / 100	233 ms	392732 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]==-2) return INF;
    if (memo[a][b][r]!=-1) return memo[a][b][r];
    memo[a][b][r] = -2;
    if (r && a+1==b) return 0;
    if (!r && a==b) return 0;
    if (r){
        long long ans = INF;
        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]);
            }
        }
        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]);
            }
        }
        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 (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]);
            }
        }
        return memo[a][b][r] = ans;
    }
    else{
        long long ans = INF;
        if (arr[a+1]>arr[a] && 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[a+1]<arr[a] && min(arr[b],arr[b+1])<=arr[a+1]){
            ans = min(ans,dp(a+1,b,false)+arr[a]-arr[a+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 (arr[b]>=arr[a-1]){
                ans = min(ans,dp(a-1,b,true)+arr[a]-arr[b]);
            }
        }
        else{
            if (arr[a+1]>=arr[b]){
                ans = min(ans,dp(a,b,true)+arr[b]-arr[a]);
            }
            else if (arr[a-1]>=arr[b]){
                ans = min(ans,dp(a-1,b,true)+arr[b]-arr[a]);
            }
        }
        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("-1");
    }
    else
        printf("%lld",res);
}

Compilation message (stderr)

climbers.cpp: In function 'int main()':
climbers.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
climbers.cpp:79: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: 0 / 50