oj.uz

Submission #261756

# Submission time Handle Problem Language Result Execution time Memory
261756 2020-08-12T04:24:16 Z cheeheng Climbers (RMI18_climbers) C++14
0 / 100
 488 ms 397576 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> ii;

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

int h2[40005];

unsigned short dist[10005][10005];

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));
            }
        }

    }
    throw;

    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 359 ms 397528 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 404 ms 397576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 10 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 14 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 14 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 410 ms 397172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 406 ms 397272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 488 ms 396984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 428 ms 397276 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 388 ms 397432 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 419 ms 397444 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 10 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 10 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 10 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 11 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 11 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 10 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 11 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 11 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 11 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)