Logs
Given an N x M binary matrix, find the area of the biggest rectangle consisting entirely of values of 1, knowing that you can permute the columns of the matrix.
Constraints
• 1 ≤ N ≤ 15000
• 1 ≤ M ≤ 1500
• 30% of the test cases will have N,M ≤ 1024
At the end of these two pieces of code, s will contain the first line of the matrix.
InputThe first line of the input file logs.in will contain two integers separated by one space: N and M. The following N lines will contain M characters of 0 or 1, describing the matrix.
OutputThe only line of the output file logs.out will contain the area of the largest rectangle.
Input:
10 6
001010
111110
011110
111110
011110
111111
110111
110111
000101
010101Output:
21Explanation
By permuting the columns such that columns 2, 4 and 5 are adjacent you have a rectangle of area 21 (rows 2-8 and columns 2, 4, 5).
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.