fork(1) download 
  1. /* paiza POH! vol.2
  2.  * result:
  3.  * http://p...content-available-to-author-only...a.jp/poh/paizen/result/2455d43008c0a1c7eaf5fe3cfa6e191d
  4.  * author: Leonardone @ NEETSDKASU
  5.  */
  6. #include <stdio.h>
  7.  
  8. int space2left[300][300];
  9. int table[301][301];
  10. int cache[301][301];
  11.  
  12. int spaceCount, count;
  13.  
  14. int main(void) {
  15. 	int H, W, N, s, t, i, j, x, y;
  16. 	char str[310];
  17.  
  18. 	scanf("%d %d", &H, &W);
  19.  
  20. 	for (y = 0; y < H; ++y) {
  21. 		scanf("%s", str);
  22. 		spaceCount = 0;
  23. 		for (x = 0; x < W; ++x) {
  24. 			if (str[x] == '0') {
  25. 				++spaceCount;
  26. 			} else {
  27. 				spaceCount = 0;
  28. 			}
  29. 			space2left[y][x] = spaceCount;
  30. 		}
  31. 	}
  32.  
  33. 	for (y = 0; y < H; ++y) {
  34. 		for (x = W - 1; x >= 0; --x) {
  35. 			if (space2left[y][x] == 0) {
  36. 				continue;
  37. 			}
  38. 			s = 1;
  39. 			t = space2left[y][x];
  40. 			for (i = y; i < H && space2left[i][x] > 0; i++) {
  41. 				if (space2left[i][x] < t) {
  42. 					t = space2left[i][x];
  43. 				}
  44. 				++table[s][t];
  45. 				++s;
  46. 			}
  47. 		}
  48. 	}
  49.  
  50. 	scanf("%d", &N);
  51.  
  52. 	for (i = 0; i < N; ++i) {
  53. 		scanf("%d %d", &s, &t);
  54.  
  55. 		count = 0;
  56.  
  57. 		if (s <= H && t <= W) {
  58. 			if (cache[s][t]) {
  59. 				count = cache[s][t] - 1 ;
  60. 			} else {
  61. 				for (j = t; j <= W; ++j) {
  62. 					count += table[s][j];
  63. 				}
  64. 				cache[s][t] = count + 1;
  65. 			}
  66. 		}
  67.  
  68. 		printf("%d\n", count);
  69. 	}
  70.  
  71. 	return 0;
  72. }
  73.  
Success #stdin #stdout 0s 3308KB
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/WUO5rj
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!