시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)36518510260.000%

문제

You are given an $N \times M$ matrix $A$. You are also given a special kernel of size $K \times K$, and a stride $S$. Your task is to implement a convolution-like operation using a kernel with unique properties. The kernel must always remain completely within the matrix boundaries during its operation.

Specifically, the unique features of a kernel in this problem are:

  • The kernel size $K$ is always an odd number.
  • The kernel is filled with $1$ along the horizontal and vertical axes passing through the center and $0$ elsewhere.

For example, the following is the kernel when the size is $3$ and $5$, respectively.

\[\begin{bmatrix} 0 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 0 \end{bmatrix} \qquad \begin{bmatrix} 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \end{bmatrix}\]

The stride determines the step size for moving the kernel across the matrix. The kernel moves across the matrix based on the given stride. At each valid position (where the kernel fits entirely within the matrix boundaries), the element-wise sum of the matrix elements covered by the kernel is calculated.

Calculate a new matrix $B$ containing the sums from all valid kernel positions. The size of $B$ should be $\left(\frac{N-K}{S}+1\right) \times \left(\frac{M-K}{S}+1\right)$.

입력

The first line contains four space-separated integers: $N$ and $M$, denoting the size of the image; $ K$, denoting the kernel size; and $S$, denoting the stride. ($1 \le N,M \le 2\,000;$ $1 \le K, S \le \min⁡\{N,M\};$ $K \equiv 1 \pmod 2;$ $S$ is a divisor of $\gcd(N-K,M-K)$)

The following $N$ lines of input contain $NM$ integers, where each line has $M$ space-separated integers, denoting the value of the matrix $A$. Here, the $j$-th integer of the $i$-th line denotes $A_{ij}$. ($-10^6 \le A_{ij} \le 10^6$)

출력

Output $\left(\frac{N-K}{S}+1\right)$ lines denoting the resulting matrix $B$ after applying the kernel with the given stride.

Each line should contain $\left(\frac{M-K}{S}+1\right)$ space-separated integers. The $j$-th integer of the $i$-th line should represent $B_{ij}$​.

서브태스크 1 (40점)

Modified constraints apply: $1 \le N,M \le 30$.

서브태스크 2 (35점)

Modified constraints apply: $1 \le N,M \le 300;$ $S=1$.

서브태스크 3 (15점)

Modified constraints apply: $1 \le N,M \le 2\,000;$ $S=1$.

서브태스크 4 (10점)

Original constraints apply: $1 \le N,M \le 2\,000$.

예제 입력 1

5 5 3 1
1 2 3 4 5
5 6 7 8 9
9 8 7 6 5
4 3 2 1 0
0 1 2 3 4

예제 출력 1

28 31 34
33 30 27
18 15 12

For the given input, the kernel size is $3$, and the stride is $1$. The initialized kernel is:

\[\begin{bmatrix} 0 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 0 \end{bmatrix}.\]

The kernel moves with a stride of $1$, and only valid positions where the kernel is fully within the matrix are considered. At each position, the sum of the overlapping matrix elements is calculated.

For example, when the upper left corner of the kernel is placed at $A_{11}$​, the value $B_{11}$​ is:

\[\begin{bmatrix} 1 & \mathbf{\color{red}2} & 3 \\ \mathbf{\color{red}5} & \mathbf{\color{red}6} & \mathbf{\color{red}7} \\ 9 & \mathbf{\color{red}8} & 7 \end{bmatrix} \rightarrow 2+5+6+7+8=28.\]

예제 입력 2

5 5 3 2
1 2 3 4 5
5 6 7 8 9
9 8 7 6 5
4 3 2 1 0
0 1 2 3 4

예제 출력 2

28 34
18 12

채점 및 기타 정보

  • 예제는 채점하지 않는다.