Status:  Past  Start:  20111201 14:00:00  End:  20111201 19:10:00 
The Caribbean Training Contest #29
Problem
1643  Searching for Stars
Created by  Yonny Mondelo Hernández 
Added by  ymondelo20 (20111129) 
Limits 
Total Time: 50000 MS

Test Time:
10000 MS
Memory: 62 MB  Output: 64 MB  Size:
29 KB

Enabled languages  
Available in 
Description
A young programmer Vasha can't get this question out of his head! How many stars are there in the sky? He took a photo of the sky using his digital camera and now he analyzes the resulting monochrome digital picture. The picture is represented by a rectangular matrix consisting of N lines each containing M characters. A character equals '1', if the corresponding photo pixel is white and '0', if it is black.
Vasha thinks that he has found a star on the photo if he finds a white pixel surrounded by four sideneighboring pixels that are also white:
1
111
1
a star on the photo.
Vasha wish to cut out a rectangular area from the photo which contain no less than K stars. The stars can intersect, have shared white pixels on the photo. Vasha will cut out the rectangular area so that its borders will be parallel to the sides of the photo and the cuts will go straight between the pixel borders.
So easy, it said. But Vasha keeps wondering how many ways there are to cut an area out of the photo so that it met the conditions given above. Can you help Vasha for finding this number.
Vasha thinks that he has found a star on the photo if he finds a white pixel surrounded by four sideneighboring pixels that are also white:
1
111
1
a star on the photo.
Vasha wish to cut out a rectangular area from the photo which contain no less than K stars. The stars can intersect, have shared white pixels on the photo. Vasha will cut out the rectangular area so that its borders will be parallel to the sides of the photo and the cuts will go straight between the pixel borders.
So easy, it said. But Vasha keeps wondering how many ways there are to cut an area out of the photo so that it met the conditions given above. Can you help Vasha for finding this number.
A young programmer Vasha can't get this question out of his head! How many stars are there in the sky? He took a photo of the sky using his digital camera and now he analyzes the resulting monochrome digital picture. The picture is represented by a rectangular matrix consisting of N lines each containing M characters. A character equals '1', if the corresponding photo pixel is white and '0', if it is black.
Vasha thinks that he has found a star on the photo if he finds a white pixel surrounded by four sideneighboring pixels that are also white:
1
111
1
a star on the photo.
Vasha wish to cut out a rectangular area from the photo which contain no less than K stars. The stars can intersect, have shared white pixels on the photo. Vasha will cut out the rectangular area so that its borders will be parallel to the sides of the photo and the cuts will go straight between the pixel borders.
So easy, it said. But Vasha keeps wondering how many ways there are to cut an area out of the photo so that it met the conditions given above. Can you help Vasha for finding this number.
Vasha thinks that he has found a star on the photo if he finds a white pixel surrounded by four sideneighboring pixels that are also white:
1
111
1
a star on the photo.
Vasha wish to cut out a rectangular area from the photo which contain no less than K stars. The stars can intersect, have shared white pixels on the photo. Vasha will cut out the rectangular area so that its borders will be parallel to the sides of the photo and the cuts will go straight between the pixel borders.
So easy, it said. But Vasha keeps wondering how many ways there are to cut an area out of the photo so that it met the conditions given above. Can you help Vasha for finding this number.
A young programmer Vasha can't get this question out of his head! How many stars are there in the sky? He took a photo of the sky using his digital camera and now he analyzes the resulting monochrome digital picture. The picture is represented by a rectangular matrix consisting of N lines each containing M characters. A character equals '1', if the corresponding photo pixel is white and '0', if it is black.
Vasha thinks that he has found a star on the photo if he finds a white pixel surrounded by four sideneighboring pixels that are also white:
1
111
1
a star on the photo.
Vasha wish to cut out a rectangular area from the photo which contain no less than K stars. The stars can intersect, have shared white pixels on the photo. Vasha will cut out the rectangular area so that its borders will be parallel to the sides of the photo and the cuts will go straight between the pixel borders.
So easy, it said. But Vasha keeps wondering how many ways there are to cut an area out of the photo so that it met the conditions given above. Can you help Vasha for finding this number.
Vasha thinks that he has found a star on the photo if he finds a white pixel surrounded by four sideneighboring pixels that are also white:
1
111
1
a star on the photo.
Vasha wish to cut out a rectangular area from the photo which contain no less than K stars. The stars can intersect, have shared white pixels on the photo. Vasha will cut out the rectangular area so that its borders will be parallel to the sides of the photo and the cuts will go straight between the pixel borders.
So easy, it said. But Vasha keeps wondering how many ways there are to cut an area out of the photo so that it met the conditions given above. Can you help Vasha for finding this number.
Input specification
The first line of the input contains three integers N, M, and K (1 <= N,M <= 500; 1 <= K <= N*M). Then follow N lines, containing the description of the given photo as a sequence of lines. Each line contains M characters '0' or '1'.
The first line of the input contains three integers N, M, and K (1 <= N,M <= 500; 1 <= K <= N*M). Then follow N lines, containing the description of the given photo as a sequence of lines. Each line contains M characters '0' or '1'.
The first line of the input contains three integers N, M, and K (1 <= N,M <= 500; 1 <= K <= N*M). Then follow N lines, containing the description of the given photo as a sequence of lines. Each line contains M characters '0' or '1'.
Output specification
The number of ways for cut an area out of the given photo, so that it met the conditions given above.
The number of ways for cut an area out of the given photo, so that it met the conditions given above.
The first line of the input contains three integers N, M, and K (1 <= N,M <= 500; 1 <= K <= N*M). Then follow N lines, containing the description of the given photo as a sequence of lines. Each line contains M characters '0' or '1'.
Sample input
5 5 4
11111
11111
11111
11111
11111
Sample output
9
Hint(s)
We'll number the rows and columns below starting from 1, the coordinates (r, c) will denote a cell in row r, column c. Then, in the sample any rectangle whose each side is no less than four, will do. The possible rectangle sizes are 4 × 4, 4 × 5, 5 × 4 and 5 × 5. Such figures can be cut in 4 ways, 2 ways, 2 ways and 1 way correspondingly.
We'll number the rows and columns below starting from 1, the coordinates (r, c) will denote a cell in row r, column c. Then, in the sample any rectangle whose each side is no less than four, will do. The possible rectangle sizes are 4 × 4, 4 × 5, 5 × 4 and 5 × 5. Such figures can be cut in 4 ways, 2 ways, 2 ways and 1 way correspondingly.
We'll number the rows and columns below starting from 1, the coordinates (r, c) will denote a cell in row r, column c. Then, in the sample any rectangle whose each side is no less than four, will do. The possible rectangle sizes are 4 × 4, 4 × 5, 5 × 4 and 5 × 5. Such figures can be cut in 4 ways, 2 ways, 2 ways and 1 way correspondingly.