fork(1) download
copy 
  1. /* paiza POH!vol.2
  2.  * result:
  3.  * http://p...content-available-to-author-only...a.jp/poh/paizen/result/e370e3de4bfd72adab6ff141d565b5cd
  4.  * author: Leonardone @ NEETSDKASU
  5.  */
  6. #include <stdio.h>
  7.  
  8. #define SIZE (9000000)
  9.  
  10. char input[SIZE];
  11. char *ptr = input;
  12.  
  13. int getInt(void) {
  14. 	int v = 0;
  15. 	while (*ptr < '0' || *ptr > '9') ++ptr;
  16. 	while (*ptr >= '0' && *ptr <= '9')
  17. 	{
  18. 		v = 10 * v + (int)(*ptr - '0');
  19. 		++ptr;
  20. 	}
  21. 	return v;
  22. }
  23.  
  24. char getChar(void) {
  25. 	while (*ptr < '0' || *ptr > '9') ++ptr;
  26. 	return *ptr++;
  27. }
  28.  
  29. void putInt(int v) {
  30. 	if (v < 10) {
  31. 		putchar('0' + (char)v);
  32. 	} else {
  33. 		putInt(v / 10);
  34. 		putchar('0' + (char)(v % 10));
  35. 	}
  36. }
  37.  
  38. int home[310][310];
  39. int hoge[310][310];
  40. int result[310][310];
  41.  
  42. int main(void) {
  43. 	int H, W, N, s, t;
  44. 	int x, y, c, i;
  45. 	int hx, hy, hxe, hye;
  46. 	int count, dy, dx;
  47. 	char ch;
  48.  
  49. 	fread(input, sizeof(char), SIZE, stdin);
  50. 	H = getInt();
  51. 	W = getInt();
  52.  
  53. 	for (y = 0; y < H; ++y) {
  54. 		c = 0;
  55. 		for (x = 0; x < W; ++x) {
  56. 			ch = getChar();
  57. 			if (ch == '0') {
  58. 				c++;
  59. 				if (y) {
  60. 					hoge[y][x] = hoge[y - 1][x] + 1;
  61. 				} else {
  62. 					hoge[y][x] = 1;
  63. 				}
  64. 			} else {
  65. 				c = 0;
  66. 				hoge[y][x] = 0;
  67. 			}
  68. 			home[y][x] = c;
  69. 		}
  70. 	}
  71.  
  72. 	N = getInt();
  73.  
  74.  
  75. 	if (W > H) {
  76. 		for (i = 0; i < N; ++i) {
  77. 			s = getInt();
  78. 			t = getInt();
  79.  
  80. 			if (s > H || t > W) {
  81. 				putchar('0');
  82. 				putchar('\n');
  83. 				continue;
  84. 			}
  85.  
  86. 			if (result[s][t]) {
  87. 				putInt(result[s][t] - 1);
  88. 				putchar('\n');
  89. 				continue;
  90. 			}
  91.  
  92. 			hye = s - 1;
  93. 			hxe = t - 1;
  94. 			count = 0;
  95. 			for (hy = H - 1; hy >= hye; --hy) {
  96. 				for (hx =  W - 1; hx >= hxe; --hx) {
  97. 					if (home[hy][hx] < t) {
  98. 						hx -= home[hy][hx];
  99. 						continue;
  100. 					}
  101. 					if (hoge[hy][hx] < s) {
  102. 						continue;
  103. 					}
  104. 					for (dy = 1; dy < s; ++dy) {
  105. 						y = hy - dy;
  106. 						if (y < 0) {
  107. 							break;
  108. 						}
  109. 						if (home[y][hx] < t) {
  110. 							break;
  111. 						}
  112. 					}
  113. 					if (dy == s) {
  114. 						count++;
  115. 					}
  116. 				}
  117. 			}
  118. 			putInt(count);
  119. 			putchar('\n');
  120. 			result[s][t] = count + 1;
  121. 		}
  122. 	} else {
  123. 		for (i = 0; i < N; ++i) {
  124. 			s = getInt();
  125. 			t = getInt();
  126.  
  127. 			if (s > H || t > W) {
  128. 				putchar('0');
  129. 				putchar('\n');
  130. 				continue;
  131. 			}
  132.  
  133. 			if (result[s][t]) {
  134. 				putInt(result[s][t] - 1);
  135. 				putchar('\n');
  136. 				continue;
  137. 			}
  138.  
  139. 			hye = s - 1;
  140. 			hxe = t - 1;
  141. 			count = 0;
  142. 			for (hx =  W - 1; hx >= hxe; --hx) {
  143. 				for (hy = H - 1; hy >= hye; --hy) {
  144. 					if (home[hy][hx] < t) {
  145. 						continue;
  146. 					}
  147. 					if (hoge[hy][hx] < s) {
  148. 						hy -= hoge[hy][hx];
  149. 						continue;
  150. 					}
  151. 					for (dy = 1; dy < s; ++dy) {
  152. 						y = hy - dy;
  153. 						if (y < 0) {
  154. 							break;
  155. 						}
  156. 						if (home[y][hx] < t) {
  157. 							break;
  158. 						}
  159. 					}
  160. 					if (dy == s) {
  161. 						count++;
  162. 					}
  163. 				}
  164. 			}
  165. 			putInt(count);
  166. 			putchar('\n');
  167. 			result[s][t] = count + 1;
  168. 		}
  169. 	}
  170.  
  171. 	return 0;
  172. }
  173.  
Success #stdin #stdout 0s 12168KB
comments (?)
stdin
copy 
5 5
00000
00100
00010
10001
10000
3
2 2
1 1
3 2
stdout
copy 
6
20
2
https://ideone.com/mXZH3K
language:
C (gcc 8.3)
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!