fork(1) download 
  1. /* paiza POH! vol.2
  2.  * result:
  3.  * http://p...content-available-to-author-only...a.jp/poh/paizen/result/fe965782d45f70aeef2f48cfbb70e0e4
  4.  * author: Leonardone @ NEETSDKASU
  5.  */
  6. import java.util.*;
  7. import java.lang.*;
  8. import java.io.*;
  9.  
  10. class Main
  11. {
  12. 	public static void main (String[] args) throws java.lang.Exception
  13. 	{
  14. 		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  15.  
  16. 		String[] hw = in.readLine().split(" ", 2);
  17. 		final int H = Integer.parseInt(hw[0]);
  18. 		final int W = Integer.parseInt(hw[1]);
  19. 		final String NEWLINE = System.getProperty("line.separator");
  20.  
  21. 		int[][] space2left = new int[H][W];
  22. 		int[][] space2top = new int[H][W];
  23. 		int allSpaceCount = 0;
  24.  
  25. 		int[] startPointX = new int[H * (1 + W / 3)];
  26. 		int[] startPointY = new int[H * (1 + W / 3)];
  27. 		int startPointCount = 0;
  28.  
  29. 		int[] space2leftCount = new int[W + 1];
  30. 		int[] space2topCount = new int[H + 1];
  31.  
  32. 		int maxSpace2leftLen = 0;
  33. 		int maxSpace2topLen = 0;
  34.  
  35. 		int[] tempSP2Ty1 = null;;
  36.  
  37. 		for (int y = 0; y < H; y++)
  38. 		{
  39. 			int[] tempSP2Ty = space2top[y];
  40. 			String line = in.readLine();
  41. 			int spaceCount = 0;
  42. 			for (int x = 0; x < W; x++)
  43. 			{
  44. 				if (line.charAt(x) == '0') // 空
  45. 				{
  46. 					spaceCount++;
  47. 					allSpaceCount++;
  48. 					if (y > 0)
  49. 					{
  50. 						int tempCount = tempSP2Ty[x] = tempSP2Ty1[x] + 1;
  51. 						if (y == H - 1 && tempCount > 1)
  52. 						{
  53. 							space2topCount[tempCount]++;
  54. 							if (tempCount > maxSpace2topLen)
  55. 							{
  56. 								maxSpace2topLen = tempCount;
  57. 							}
  58. 						}
  59. 					}
  60. 					else // if (y == 0) 
  61. 					{
  62. 						tempSP2Ty[x] = 1;
  63. 					}
  64. 				}
  65. 				else // if (ch == '1') // 埋
  66. 				{
  67. 					if (spaceCount > 1)
  68. 					{
  69. 						startPointX[startPointCount] = x - 1;
  70. 						startPointY[startPointCount] = y;
  71. 						startPointCount++;
  72. 						space2leftCount[spaceCount]++;
  73. 						if (spaceCount > maxSpace2leftLen)
  74. 						{
  75. 							maxSpace2leftLen = spaceCount;
  76. 						}
  77. 					}
  78. 					spaceCount = 0;
  79. 					// space2top[y][x] = 0; // 初期値のまんま
  80. 					if (y > 0) {
  81. 						space2topCount[tempSP2Ty1[x]]++;
  82. 						if (tempSP2Ty1[x] > maxSpace2topLen)
  83. 						{
  84. 							maxSpace2topLen = tempSP2Ty1[x];
  85. 						}
  86. 					}
  87. 				}
  88. 				space2left[y][x] = spaceCount;
  89. 			} // for(x)
  90. 			if (spaceCount > 1)
  91. 			{
  92. 				startPointX[startPointCount] = W - 1;
  93. 				startPointY[startPointCount] = y;
  94. 				startPointCount++;
  95. 				space2leftCount[spaceCount]++;
  96. 				if (spaceCount > maxSpace2leftLen)
  97. 				{
  98. 					maxSpace2leftLen = spaceCount;
  99. 				}
  100. 			}
  101. 			tempSP2Ty1 = tempSP2Ty;
  102. 		} // for(y)
  103.  
  104. 		final int N = Integer.parseInt(in.readLine());
  105. 		int[][] result = new int[301][301];
  106.  
  107. 		result[1][1] = allSpaceCount + 1;
  108. 		for (int i = 2; i <= maxSpace2topLen; i++) 
  109. 		{
  110. 			int count = 0;
  111. 			for (int j = i; j <= maxSpace2topLen; j++)
  112. 			{
  113. 				count += space2topCount[j] * (j - i + 1);
  114. 			}
  115. 			result[i][1] = count + 1;
  116. 		}
  117. 		for (int i = maxSpace2topLen; i <= H; i++)
  118. 		{
  119. 			result[i][1] = 1;
  120. 		}
  121. 		for (int i = 2; i <= maxSpace2leftLen; i++) 
  122. 		{
  123. 			int count = 0;
  124. 			for (int j = i; j <= maxSpace2leftLen; j++)
  125. 			{
  126. 				count += space2leftCount[j] * (j - i + 1);
  127. 			}
  128. 			result[1][i] = count + 1;
  129. 		}
  130. 		for (int i = maxSpace2leftLen; i <= W; i++)
  131. 		{
  132. 			result[1][i] = 1;
  133. 		}
  134.  
  135. 		StringBuilder output = new StringBuilder(N * (6 + NEWLINE.length()));
  136.  
  137. 		for (int i = 0; i < N; i++)
  138. 		{
  139. 			String[] st = in.readLine().split(" ", 2);
  140. 			int s = Integer.parseInt(st[0]);
  141. 			int t = Integer.parseInt(st[1]);
  142.  
  143. 			int count = 0;
  144.  
  145. 			if (s <= H && t <= W)
  146. 			{
  147. 				if (result[s][t] > 0)
  148. 				{
  149. 					count = result[s][t] - 1;
  150. 				}
  151. 				else // if (s != 1 && t != 1)
  152. 				{
  153. 					for (int j = 0; j < startPointCount; j++)
  154. 					{
  155. 						int x = startPointX[j];
  156. 						int y = startPointY[j];
  157. 						int seekLength = space2left[y][x] - t + 1;
  158.  
  159. 						int[] tempSP2Ty = space2top[y];
  160. 						for (int dx = 0; dx < seekLength; dx++)
  161. 						{
  162. 							int tx = x - dx;
  163. 							if (tempSP2Ty[tx] < s)
  164. 							{
  165. 								continue;
  166. 							}
  167. 							int dy;
  168. 							for (dy = 0; dy < s; dy++)
  169. 							{
  170. 								if (space2left[y - dy][tx] < t)
  171. 								{
  172. 									break;
  173. 								}
  174. 							} // for(dy)
  175. 							if (dy == s)
  176. 							{
  177. 								count++;
  178. 							}
  179. 						} // for(dx)
  180. 					} // for(j)
  181. 				}
  182. 			}
  183. 			output.append(count);
  184. 			output.append(NEWLINE);
  185. 			result[s][t] = count + 1;
  186. 		} // for(i)
  187.  
  188. 		System.out.print(output);
  189.  
  190. 	} // void main([String)
  191.  
  192. } // class Main
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin 
5 5
00000
00100
00010
10001
10000
7
2 2
1 1
3 2
3 2
2 3
3 1
1 3
stdout 
6
20
2
2
1
6
7
https://ideone.com/nVKTj7
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!