Chef and Rectangle Array
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef has a two-dimensional matrix A of dimensions N × M, (N rows and M columns).
He calls the matrix A beautiful if there exist an a×b submatrix, such that all of its elements are equal. In one minute Chef can increase one element of the matrix A by 1. Now he asks you to find out minimum time he will need to make the matrix A beautiful?
Please note that sub-matrix of a matrix is a continuous rectangular block of the matrix. It can be denoted by two pair of indices (x1, y1) and (x2, y2) where x1 ≤ x2, y1 ≤ y2. The content of the submatrix will be all the cells (i, j) such that x1 ≤ i ≤ x2 and y1 ≤ j ≤ y2.
- There is a single test case.
- The first line contains two space-separated integers N, M denoting the number of rows and columns in the matrix A, respectively
- Each of the next N lines, contains M space-separated integers denoting the i-th row of the array
- Next line contains one integer Q - amount of questions
- Each of next Q lines contains two space-separated integers a and b denoting sizes of submatrix sought.
- All questions are independent and do not influence each other. It means when you answer question, you don't need to change the array
- 1 ≤ Q ≤ 50
- 1 ≤ N, M, Ai, j ≤ 1000
- 1 ≤ a ≤ N
- 1 ≤ b ≤ M
Subtask #1 (13 pts)
- 1 ≤ N, M ≤ 50
- TL = 1s
Subtask #2 (35 pts)
- 1 ≤ N, M ≤ 200
- TL = 2s
Subtask #3 (52 pts)
- Original constraints
- TL = 4s
Input: 3 4 1 8 3 4 5 2 3 1 3 6 2 2 4 1 1 2 2 2 3 3 2 Output: 0 4 15 9
Chef can choose any 1 × 1 submatrix and it will take his 0 minutes to make it beautiful.
The best variant is submatrix
3 1 2 2
The next submatrix Chef can make equal in 15 minutes
5 2 3 3 6 2
3 4 3 1 2 2
|Tags||antoniuk1, dynamic-programming, june16, medium, partial-sums|
|Time Limit:||1 - 4 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, 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
If you are still having problems, see a sample solution here.