oj.uz

Submission #261692

# Submission time Handle Problem Language Result Execution time Memory
261692 2020-08-12T01:57:10 Z tqbfjotld Climbers (RMI18_climbers) C++14
5 / 100
 233 ms 392732 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 214 ms 392440 KB Output isn't correct
2 Incorrect 212 ms 392440 KB Output isn't correct
3 Incorrect 221 ms 392440 KB Output isn't correct
4 Incorrect 209 ms 392468 KB Output isn't correct
5 Incorrect 219 ms 392568 KB Output isn't correct

Subtask #2
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 392568 KB Output is correct
2 Incorrect 233 ms 392568 KB Output isn't correct
3 Incorrect 217 ms 392732 KB Output isn't correct
4 Incorrect 210 ms 392440 KB Output isn't correct
5 Incorrect 211 ms 392568 KB Output isn't correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 215 ms 392448 KB Output isn't correct
2 Incorrect 211 ms 392440 KB Output isn't correct
3 Incorrect 214 ms 392440 KB Output isn't correct
4 Incorrect 215 ms 392488 KB Output isn't correct
5 Incorrect 213 ms 392488 KB Output isn't correct
6 Incorrect 212 ms 392568 KB Output isn't correct
7 Incorrect 212 ms 392524 KB Output isn't correct
8 Incorrect 213 ms 392568 KB Output isn't correct
9 Incorrect 214 ms 392568 KB Output isn't correct
10 Incorrect 212 ms 392568 KB Output isn't correct