oj.uz

Submission #261753

# Submission time Handle Problem Language Result Execution time Memory
261753 2020-08-12T04:22:46 Z cheeheng Climbers (RMI18_climbers) C++14
5 / 100
 270 ms 297304 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> ii;

int h[5005];
int h3[5005];

int h2[25000005];

int dist[5005][5005];

int main(){
    int N;
    scanf("%d", &N);

    for(int i = 0; i < N; i ++){
        scanf("%d", &h[i]);
    }


    int P = 2;
    h3[0] = h[0];
    h3[1] = h[1];
    for(int i = 2; i < N; i ++){
        if(h3[i-2] >= h3[i-1] && h3[i-1] >= h3[i]){

        }
    }

    int M = 1;
    h2[0] = 0;
    for(int i = 0; i < N-1; i ++){
        if(h[i] < h[i+1]){
            for(int j = h[i]+1; j <= h[i+1]; j ++){
                h2[M++] = j;
            }
        }else if(h[i] > h[i+1]){
            for(int j = h[i]-1; j >= h[i+1]; j --){
                h2[M++] = j;
            }
        }
    }

    /*
    for(int i = 0; i < M; i ++){
        printf("%d ", h2[i]);
    }
    printf("\n");
    */

    for(int i = 0; i < M; i ++){
        //printf("h2[%d]=%d\n", i, h2[i]);
    }

    long long ans = 0;
    int A = 0;
    int B = M-1;
    memset(dist, -1, sizeof(dist));
    dist[A][B] = 0;
    queue<ii> q;
    q.push(ii(A, B));
    while(!q.empty()){
        int A, B;
        tie(A, B) = q.front(); q.pop();
        if(A == B){
            printf("%d\n", dist[A][B]);
            return 0;
        }
        //printf("while loop: %d %d %d\n", A, B, dist[A][B]);
        //printf("%d %d %d %d\n", h2[A+1], h2[A-1], h2[B+1], h2[B-1]);
        //if(ans > 100){break;}
        if(h2[A+1] == h2[B-1]){
            if(dist[A+1][B-1] == -1){
                dist[A+1][B-1] = dist[A][B]+1;
                q.push(ii(A+1, B-1));
            }
        }

        if(h2[A-1] == h2[B-1]){
            if(dist[A-1][B-1] == -1){
                dist[A-1][B-1] = dist[A][B]+1;
                q.push(ii(A-1, B-1));
            }
        }
        if(h2[A+1] == h2[B+1]){
            if(dist[A+1][B+1] == -1){
                dist[A+1][B+1] = dist[A][B]+1;
                q.push(ii(A+1, B+1));
            }
        }

    }

    ans = 1LL << 61;
    for(int i = 0; i < M; i ++){
        if(dist[i][i] == -1){continue;}
        ans = min(ans, (long long)dist[i][i]);
    }

    if(ans == (1LL << 61)){
        printf("NO");
        return 0;
    }

    printf("%lld\n", ans);
    return 0;
}

Compilation message

climbers.cpp: In function 'int main()':
climbers.cpp:22:9: warning: unused variable 'P' [-Wunused-variable]
     int P = 2;
         ^
climbers.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
climbers.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &h[i]);
         ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 182 ms 199544 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 175 ms 204024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 270 ms 297304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 190 ms 198776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 188 ms 198780 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 98424 KB Output is correct
2 Incorrect 55 ms 98328 KB Output isn't correct
3 Runtime error 186 ms 199288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 190 ms 199416 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 184 ms 199416 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 199 ms 207612 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 214 ms 240636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 191 ms 198776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 214 ms 198776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 187 ms 198776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 188 ms 198776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 175 ms 198776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 188 ms 198904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 193 ms 198780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 193 ms 198776 KB Execution killed with signal 11 (could be triggered by violating memory limits)