제출 #1318004

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1318004		aris12345678	밀림 점프 (APIO21_jumps)	C++17	0 / 100	4043 ms	10228 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> height, dist;
vector<vector<int>> adj;

void init(int N, vector<int> H) {
    n = N;
    height = H;
    adj.resize(N);
    for(int i = 0; i < N; i++) {
        for(int j = i-1; j >= 0; j--) {
            if(H[j] > H[i]) {
                adj[i].push_back(j);
                break;
            }
        }
        for(int j = i+1; j < n; j++) {
            if(H[j] > H[i]) {
                adj[i].push_back(j);
                break;
            }
        }
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    queue<int> q;
    dist.assign(n, INT_MAX);
    for(int i = A; i <= B; i++) {
        q.push(i);
        dist[i] = 0;
    }
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        if(u >= C && u <= D) continue;
        for(int i = 0; i < adj[u].size(); i++) {
            if(dist[adj[u][i]] > dist[u]+1) {
                q.push(adj[u][i]);
                dist[adj[u][i]] = dist[u]+1;
            }
        }
    }
    int ans = INT_MAX;
    for(int i = C; i <= D; i++)
        ans = min(ans, dist[i]);
    return ans; 
    if(ans == INT_MAX) return -1;
    return ans;
}

// int main() {
//     int N, Q;
//     scanf("%d %d", &N, &Q);
//     vector<int> H(N);
//     for(int i = 0; i < N; i++)
//         scanf("%d", &H[i]);
//     init(N, H);
//     while(Q--) {
//         int A, B, C, D;
//         scanf("%d %d %d %d", &A, &B, &C, &D);
//         printf("%d\n", minimum_jumps(A, B, C, D));
//     }
//     return 0;
// }

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19