Maximum Subrectangle in Matrix

All submissions for this problem are available.
You are given a matrix of the size H × W with integer elements. So it has H rows and W columns. The rows are numbered by integers in the range [0, H – 1] while for the columns the range [0, W – 1] is used. Your task is to find out a subrectangle of this matrix with a large sum. The sum of a subrectangle is the sum of all its elements. However, subrectangle does not need to be contiguous. More formally, you have to find out a subset of rows R and a subset of columns C. Then your subrectangle contains all those cells (r, c) where r is in R and c is in C.
This is a challenge problem so you don't have to find out the optimal solution. You would get a partial score depending on how large the sum of your chosen rectangle is.
Input
The first line of the input contains two space separated integers H and W, the height and the width of the matrix respectively. Each of the following H lines contains W space separated integers, the elements of the corresponding row of the matrix.
Output
Your output should consist of 3 lines. The first line of the output should contain two space separated integers R_SIZE and C_SIZE, the sizes of your row set and the column set respectively. In the next line there should be R_SIZE distinct integers in the range [0, H – 1] in ascending order, the set of rows you have chosen. In the third line there should be C_SIZE distinct integers in the range [0, W – 1] in ascending order, the set of columns you have chosen.
Your program will get accepted if and only if all of the following conditions are satisfied:
 Both your row set and column set are nonempty, that is, R_SIZE ≥ 1 and C_SIZE ≥ 1.
 The second line of your output contains R_SIZE distinct integers in the range [0, H – 1] in ascending order.
 The third line of your output contains C_SIZE distinct integers in the range [0, W – 1] in ascending order.
 The sum of your chosen subrectangle is positive. You are guaranteed that such a subrectangle always exists.
Scoring
Let numerator = Sum of your chosen subrectangle
and denominator = Sum of all positive elements of the matrix.
Then your score for a single file is equal to numerator / denominator. Your total score is the average of individual scores for each file multiplied by 10000 for convenience. Your goal is to maximize your total score.
Constraints
1 ≤ H, W ≤ 300
Each element of the matrix does not exceed 10^{9} by the absolute value.
There exists a subrectangle of the given matrix which has positive sum.
In each official test file H, W ≥ 200.
Example
Input: 3 3 1 2 4 2 3 1 8 9 1 Output: 1 2 1 1 2
Explanation
In this output the set of one row R = {1} and the set of two columns C = {1, 2} have been chosen. The chosen cells of the matrix are M[1][1] = 3, M[1][2] = 1 (recall that the numeration of rows and columns is 0based). So the sum of the chosen subrectangle is 3 + (1) = 2 > 0. The sum of all positive elements of the matrix is 4 + 2 + 3 + 8 + 9 = 26. So the score you will get for such output is 2 / 26 = 0.0769231. Note that this is not the optimal solution for this matrix.
Author:  yellow_agony 
Tester:  anton_lunyov 
Editorial  http://discuss.codechef.com/problems/MAXRECT 
Tags  challenge, oct12, yellow_agony 
Date Added:  8072012 
Time Limit:  0.4 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, 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, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions