Matrix

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+x1][j+y1] equals to one. Of course, the square (i, j, i+h1, j+h1) 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.
Input
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
Output should consist of a single integer  the answer to the problem.
Example
Input: 2 3 011 111 Output: 6
Scoring
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.
Author:  xcwgf666 
Tester:  rubanenko 
Editorial  http://discuss.codechef.com/problems/MATRIX2 
Tags  dynamicprogramming, ltime03, simple, xcwgf666 
Date Added:  20072013 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, 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, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 