| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 9 | 4 | 4 | 57.143% |
You have written many programs to search mazes so matrix search shouldn’t be any different, or will it?
An integer matrix with R rows and C columns has R(R-1)/2 × C(C-1)/2 sub matrices. We want to select a sub matrix with sum (the sum of all integers in it) greater than or equal to a given integer S. We want the size of the sub matrix to be the least possible. The size of a sub matrix is defined as the number of elements in that sub matrix (i.e., number of rows * number of columns in that sub matrix).
The first input line contains a positive integer, t, indicating the number of test cases. The first line of each test case consists of three integers R, C (1 ≤ R ≤ 100,000; 1 ≤ C ≤ 100,000; 1 ≤ R*C ≤ 100,000) and S. Next R lines contain the description of the matrix. Each of these R lines contains C integers separated by a single space. All integers (other than R and C) are between -109 and +109, inclusive.
For each test case, output the size of the minimum sub matrix whose sum is greater or equal to the given S. If there is no such sub matrix, output -1.
3 3 3 26 1 2 3 4 5 6 7 8 9 3 3 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 2 2 1 -1 -2 0 2
4 -1 1