ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

2039. Striped Square

Time limit: 0.5 second
Memory limit: 64 MB
Encouraged by success of his previous paintings, Kazimir Malevich prepares to create a new masterpiece. In order to reach a whole new level of abstraction, he decided to divide the process of creation into several steps.
He started by taking a white canvas and tiling it into a grid of n × m identical square cells. After that, he painted some of the cells black. Now Malevich wants to cut out some square area along the grid lines, and he wants it to be striped. Contemporary artists define a striped area as follows: it has exactly k distinct black rows, exactly k distinct black columns and all other cells are white. Now Malevich is startled by the following question: “How many distinct ways to find a striped square are there?”. Help him understand how many distinct striped square areas can be found on the canvas. Two square areas are considered distinct if they have a different side length or different coordinates of the upper left corner.


The first line contains integers n, m and k (1 ≤ n, m, k ≤ 1000). Next n lines describe the canvas. Each line consists of m characters, each character is either ‘1’ or ‘0’. A zero means that the corresponding cell on the canvas is white, a one means that it is black.


A single line must contain the answer to the problem.


5 6 2


We will denote a square area as (R, C, L) where R and C denote the row and column of the upper left corner and L denotes its side length. In the given example, there are seven different ways to choose a squared striped area: (2, 2, 3), (1, 1, 4), (1, 2, 4), (2, 1, 4), (2, 2, 4), (1, 1, 5), (1, 2, 5).
Problem Author: Kirill Borozdin (prepared by Oleg Merkurev)
Problem Source: Ural FU Dandelion contest. Petrozavodsk training camp. Summer 2014