Battle of Legends
All submissions for this problem are available.
Two tourists named Shiv and Abhi like to travel a lot. While travelling they like to solve some puzzles too. Once while travelling in Advaitam 3.0 camps, they came to a camp where a tough puzzle is present. In the puzzle, there is a rectangular maze of size N * M. Each cell of the maze consists of value Ai, j. Shiv is obsessed with the maximum values and Abhi is obsessed with the minimum values. Now the host of the puzzle asks them to find a submatrix of size a * b. In the submatrix, Shiv will increase all the elements to the maximum value present in the submatrix while Abhi will decrease the values of submatrix to the minimum value present in the submatrix. The puzzle maker is interested in the minimum difference of the submatrix sum according to Abhi and Shiv out of all the submatrix possible.
First line contains three integers N(1 <= N <= 1000), M(1 <= M <= 1000) and Q (1 <= Q<= 20)the size of the matrix and number of queries.
Next N lines contain M space separated integers Ai, j(1 <= Ai, j <= 103) denoting the values at each cell of the matrix.
Next Q lines contains two space separated integers a(1 <= a <= N) and b(1 <= b <= M) denoting the size of the submatix.
For each of the Q queries, print the minimum difference of the sum of the maximum values and minimum values of the submatrix.
Constraints and Subtasks
Subtask 1: 20 points
3 4 5 1 2 3 4 4 3 2 1 7 8 9 10 1 1 2 3 3 2 3 4 3 3Output:
0 18 42 108 72
For the second query the submatrix with minimum difference is
1 2 3 4 3 2or
2 3 4 3 2 1The minimum of both the submatrices is 1 and maximum is 4. So Abhi will make all the elements of submatrix 1 and Shiv will make all the elements to 4. So sum of elements according to Abhi is 6 and that of Shiv is 24. So the difference is 24 - 6 = 18.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions