0

Minimise Sum

Difficulty: HARD
Contributed By
Prateek Kalyani
Avg. time to solve
45 min
Success Rate
60%

Problem Statement

You are given a matrix of ‘N’ rows and ‘M’ columns and a non-negative integer ‘K’. You have to find the minimum possible sum of all elements in each submatrix after performing most ‘K’ decrements.

Note:
You can’t decrease a number below 0.
For example:
You are given ‘K’ = 5, and matrix 
‘mat’ = [[1, 2, 3],
         [4, 0, 5],
         [2 , 7, 4]]
You can do 3 operations on element 7 and 2 operations on element 5. Then the sum of all submatrices will be 246.
Input Format:
The first line of input contains a single integer ‘T’, denoting the number of test cases.

The first line of each test case contains three space-separated integers ‘N’, ‘M’, and ‘K’, representing the rows, columns of the matrix, and the given integer.

The following ‘N’ lines of input contain ‘M’ space-separated integers representing the matrix elements.
Output Format:
For each test case, print a single integer representing the minimum possible sum of all elements in each submatrix. Print the answer in the modulo 10^9 + 7.

Print a single line for each test case.
Constraints:
1 <= T <= 10
1 <= N, M <= 500
0 <= K <= 10^12
1<= mat[i][j] <= 10^6

Time Limit: 1 sec
Sample Input 1:
2
3 3 5
1 2 3
4 0 5
2 7 4
1 2 1
3 4
Sample Output 1:
246
12
Explanation:
For the first test case, given K = 5, and matrix 
‘mat’ = [[1, 2, 3],
         [4, 0, 5],
         [2 , 7, 4]]
 You can do three operations on element 7 and 2 operations on element 5. Then the sum of all submatrices will be 246.

For the second test case, given K = 1 and the matrix
mat = [[3, 4]]
You can do one operation on element 4. Then the sum of all submatrices will be 12.
Sample Input 2:
2
2 2 4
1 2
3 4
3 3 3
1 2 3
3 4 5
5 6 7
Sample Output 2:
24
368
Reset Code
Full screen
copy-code
Console