oj.uz

Submission #261705

# Submission time Handle Problem Language Result Execution time Memory
261705 2020-08-12T02:22:54 Z tqbfjotld Climbers (RMI18_climbers) C++14
5 / 100
 229 ms 392592 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];

    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]);
            }
        }
        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 (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]);
            }
        }
        //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] && 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 (a!=0 && 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 (a!=0 && arr[a-1]>=arr[b]){
                ans = min(ans,dp(a-1,b,true)+arr[b]-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:81:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
climbers.cpp:84: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 229 ms 392440 KB Output isn't correct
2 Incorrect 227 ms 392440 KB Output isn't correct
3 Incorrect 211 ms 392436 KB Output isn't correct
4 Incorrect 213 ms 392568 KB Output isn't correct
5 Incorrect 212 ms 392592 KB Output isn't correct

Subtask #2
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 392440 KB Output is correct
2 Incorrect 207 ms 392440 KB Output isn't correct
3 Incorrect 220 ms 392528 KB Output isn't correct
4 Incorrect 205 ms 392444 KB Output isn't correct
5 Incorrect 207 ms 392440 KB Output isn't correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 206 ms 392440 KB Output isn't correct
2 Incorrect 220 ms 392572 KB Output isn't correct
3 Incorrect 210 ms 392568 KB Output isn't correct
4 Incorrect 211 ms 392440 KB Output isn't correct
5 Incorrect 209 ms 392540 KB Output isn't correct
6 Incorrect 210 ms 392440 KB Output isn't correct
7 Incorrect 209 ms 392444 KB Output isn't correct
8 Incorrect 210 ms 392536 KB Output isn't correct
9 Incorrect 217 ms 392440 KB Output isn't correct
10 Incorrect 207 ms 392440 KB Output isn't correct