하이퍼 최솟값

시간 제한2초메모리 제한256 MB

요약
변 길이가 M인 모든 4차원 부분 정육면체의 최솟값을 4차원 배열에서 구합니다.
난이도

보통10점 중 5점

유형
슬라이딩 윈도우, 큐
정답자
아직 제출이 없습니다

문제

각 차원의 인덱스가 1부터 NN까지인 4차원 배열 XX가 있다. 다음 식으로 정의되는 4차원 배열 YY를 구하라.

Y[i1,i2,i3,i4]=min⁡X[j1,j2,j3,j4]Y[i_1, i_2, i_3, i_4] = \min X[j_1, j_2, j_3, j_4]

최솟값은 각 kk에 대해 1≤ik≤N−M+11 \le i_k \le N - M + 1이고 ik≤jk≤ik+M−1i_k \le j_k \le i_k + M - 1인 모든 (j1,j2,j3,j4)(j_1, j_2, j_3, j_4)에 대해 구한다. 즉 YY의 원소 하나는 XX 안에서 한 변의 길이가 MM인 4차원 정육면체에 들어 있는 값의 최솟값이다. YY의 각 차원 크기는 N−M+1N - M + 1이다.

입력

첫 줄에 NN과 MM이 주어진다 (1≤M≤N1 \le M \le N). 다음 줄부터 배열 XX의 원소가 주어진다. 원소 개수 N4N^4은 1500000 이하이고, 각 원소는 절댓값이 10910^9 이하인 정수다. 원소는 다음 의사 코드로 읽을 수 있는 순서로 주어진다.

for i = 1 to N:
    for j = 1 to N:
        for k = 1 to N:
            for l = 1 to N:
                read X[i, j, k, l]

출력

배열 YY의 원소 (N−M+1)4(N - M + 1)^4개를 XX와 같은 순서, 즉 위 의사 코드와 같은 4중 반복문 순서로 출력한다. 모든 값을 공백 하나로 구분해 한 줄에 출력한다.

예제4

  1. 예제 1

    입력
    1 1
    1
    
    예상 출력
    1
    
  2. 예제 2

    입력
    3 2
    3 1 4 -4 0 4 0 0 -3 0 -2 -5 5 3 5 -4 4 -3 -5 -4 -4 5 -1 0 -3 -2 -1 2 -5 -5 -1 1 1 -4 3 5 3 -3 -3 3 0 1 4 -1 -2 3 -2 5 4 -1 -5 3 -4 0 -3 -1 3 -1 4 4 -1 -5 -3 4 -4 5 1 5 -4 3 2 2 -2 -2 4 2 -4 -3 1 3 1
    
    예상 출력
    -5 -5 -4 -3 -5 -5 -4 -5 -5 -5 -5 -5 -4 -5 -4 -5
    
  3. 예제 3

    입력
    2 1
    8 15 9 8 12 17 -8 -9 12 10 20 19 -9 -14 8 -1
    
    예상 출력
    8 15 9 8 12 17 -8 -9 12 10 20 19 -9 -14 8 -1
    
  4. 예제 4

    입력
    2 2
    7 -3 5 0 2 9 -1 4 6 6 -3 8 1 1 0 -2
    
    예상 출력
    -3