All submissions for this problem are available.
You are given a matrix A that consists of N rows and M columns. Every number in the matrix is either zero or one. Calculate the number of such triples (i, j, h) where for all the pairs (x, y), where both x and y belong to [1; h] if y >= x, A[i+x-1][j+y-1] equals to one. Of course, the square (i, j, i+h-1, j+h-1) should be inside of this matrix. In other words, we're asking you to calculate the amount of square submatrices of a given matrix which have ones on and above their main diagonal.
The first line of the input consists of two integers - N and M.
The following N lines describe the matrix. Each line consists of M characters that are either zero or one.
Output should consist of a single integer - the answer to the problem.
Input: 2 3 011 111 Output: 6
Subtask 1 (9 points): 1 <= N,M <= 2000, All the numbers in the matrix are equal to one.
Subtask 2 (12 points): 1 <= N,M <= 10.
Subtask 3 (34 points): 1 <= N,M <= 30.
Subtask 4 (17 points): 1 <= N,M <= 150.
Subtask 5 (28 points): 1 <= N,M <= 2000.
|Tags||dynamic-programming, ltime03, simple, xcwgf666|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, 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, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.