|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||32 MB||18||8||7||46.667%|
Humans finally landed on one of the Centaurus Constellation planets. A big surprise (or not!): the planet is inhabited by monsters! The monsters’ defense system is composed of battle cells, arranged in the form of a matrix with N rows and M columns.
Our intergalactic army has already attacked some of the cells, but now it is your turn to destroy exactly one cell.
By definition, the strength of the monsters’ defense system is equal to the number of submatrices (possibly overlapping) that contain only intact cells.A submatrix is a nonempty matrix obtained from the original matrix by eventually removing:
Select a cell to be destroyed by you in a way that minimizes the strength of the defense system.
Develop a program to calculate the strength of the defense system after your attack.
The first line of the standard input contains two space separated integers N and M representing the number of rows, and the number of columns, respectively. (1 ≤ N, M ≤ 750)
Each of the next N lines contains a binary string of size M, representing the cells of the matrix. A 1 corresponds to an intact cell, while a 0 corresponds to a cell already destroyed by our army.
There is at least one intact cell in the defense system.
Write on the single line of the standard output the strength of the defense system after your attack.
3 3 011 110 100
5 5 10110 11111 11011 00100 11011
The initial strength of the monsters’ defense system is 9. By destroying the intact cell on the intersection of the 2nd row and 2 nd column, the defense system will be of strength 6 and will look as follows:
011 100 100
The initial strength of the monsters’ defense system is 44. By destroying the intact cell on the intersection of the 2nd row and 4th column, the defense system will be of strength 31 and will look as follows:
10110 11101 11011 00100 11011