All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef recently cooked a big cake that can be represented as a grid of N rows and M columns, each cell can be either empty or contain a currant, Chef wants to cut out a sub-rectangle from the cake which contains even number of currants. Before cutting such a sub-rectangle, he is interested in knowing how many sub-rectangles are there which contains even number of currants.
There is a single test case.
First line of the input contains two integers N and M.
Each of the next N lines contains a string of length M, j-th character of i-th string is 1 if the corresponding cell contains a currant otherwise it's 0.
Output a single integer, the number of sub rectangles which contains even number of currants.
- 1 ≤ N, M ≤ 1500
Input: 2 2 01 10 Output: 3
Input: 3 4 1010 0101 1110 Output: 26
|Tags||bitwise-operatn, cook71, easy-medium, kingofnumbers|
|Time Limit:||1.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, 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, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.