시간 제한메모리 제한제출정답맞힌 사람정답 비율
7 초 (추가 시간 없음) 1024 MB333100.000%

문제

Here is an example of a small town consisting of $5 \times 5 = 25$ blocks and a population of 99. The colors highlight one way in which the town can be divided into 3 contiguous wards of 33 citizens each.

Your task is to consider towns of various sizes and determine if there is at least one way to divide up the blocks into contiguous wards of equal population. All towns will be rectangular and consist of no more than 25 blocks. The number of desired wards may vary.

A block is considered adjacent to another block if it shares an edge. A contiguous ward is a collection of blocks such that by starting at one, and only traveling to adjacent blocks in the ward, you can get to every block in the ward.

입력

The first line contains two integers $R$ and $C$ ($1 \leq R \times C \leq 25$) indicating the number of rows and columns of the rectangular town. The next line contains an integer $W$ ($1 \leq W \leq R \times C$) indicating the number of wards desired for the town. The next $R$ lines each contains $C$ non-negative integers representing the populations of the blocks of the rows, starting at the top row. The blocks in each row are listed from left to right. The total population of the town will be no more than $1{,}000{,}000$.

출력

If it is possible to do the reapportionment with the given input, print "Yes". Otherwise print "No".

예제 입력 1

5 5
3
1 4 12 7 5
8 10 9 1 2
2 4 1 2 3
3 3 5 4 3
1 2 4 2 1

예제 출력 1

Yes

출처

ICPC > Regionals > North America > North Central North America Regional > 2023 North Central NA Regional Contest I번

  • 문제를 만든 사람: Charles Riedesel