fork(1) download 
  1. /* paiza POH! vol.2
  2.  * result:
  3.  * http://p...content-available-to-author-only...a.jp/poh/paizen/result/5464496aa5968d71d782f99e2a91340c
  4.  * author: Leonardone @ NEETSDKASU
  5.  */
  6. import java.util.*;
  7. import java.lang.*;
  8. import java.io.*;
  9.  
  10. class Main
  11. {
  12. 	static int[] sp = new int[91000];
  13. 	static int[] tb = new int[91000];
  14. 	static int[] ca = new int[91000];
  15. 	static StringBuilder ou = new StringBuilder(400000);
  16.  
  17. 	public static void main (String[] args) throws java.lang.Exception
  18. 	{
  19. 		BufferedReader in = new BufferedReader(
  20. 			new InputStreamReader(System.in));
  21.  
  22. 		String[] hw = in.readLine().split(" ");
  23. 		int H = Integer.parseInt(hw[0]); // ホーム画面縦の区画数
  24. 		int W = Integer.parseInt(hw[1]); // ホーム画面横の区画数
  25.  
  26. 		int[] space2right = sp;
  27. 	 	int[] table = tb;
  28. 		int[] cache = ca;
  29.  
  30. 		int y, x, j ,i, s, t;
  31. 		String line;
  32. 		int count, all = 0;
  33.  
  34. 		for (y = 0; y < H; y++)
  35. 		{
  36. 			line = in.readLine();
  37. 			count = 0;
  38. 			for (x = W - 1; x >= 0; x--)
  39. 			{
  40. 				if (line.charAt(x) == '0')
  41. 				{
  42. 					count++;
  43. 					all++;
  44. 				}
  45. 				else
  46. 				{
  47. 					count = 0;
  48. 				}
  49. 				space2right[y * 301 + x] = count;
  50. 			}
  51. 		}
  52. 		cache[302] = all + 1;
  53.  
  54. 		j = 0;
  55. 		for (y = 0; y < H; y++)
  56. 		{
  57. 			for (x = 0; x < W; x++)
  58. 			{
  59. 				if (space2right[j + x] == 0)
  60. 				{
  61. 					continue;
  62. 				}
  63. 				s = 301;
  64. 				t = space2right[j + x];
  65. 				for (i = y; i < H && space2right[i * 301 + x] > 0; i++)
  66. 				{
  67. 					if (space2right[i * 301 + x] < t)
  68. 					{
  69. 						t = space2right[i * 301 + x];
  70. 					}
  71. 					table[s + t]++;
  72. 					s += 301;
  73. 				}
  74. 			}
  75. 			j += 301;
  76. 		}
  77.  
  78. 		int N = Integer.parseInt(in.readLine()); // ウィジェット数
  79. 		StringBuilder output = ou;
  80.  
  81. 		for (i = 0; i < N; i++)
  82. 		{
  83. 			hw = in.readLine().split(" ");
  84. 			s = Integer.parseInt(hw[0]); // ウィジェットの縦サイズ
  85. 			t = Integer.parseInt(hw[1]); // ウィジェットの横サイズ
  86.  
  87. 			count = 0;
  88. 			if (s <= H && t <= W)
  89. 			{
  90. 				y = s * 301;
  91. 				x = y + t;
  92. 				if (cache[x] > 0)
  93. 				{
  94. 					count = cache[x] - 1;
  95. 				}
  96. 				else
  97. 				{
  98. 					for (j = t; j <= W; j++)
  99. 					{
  100. 						count += table[y + j];
  101. 					}
  102. 					cache[x] = count + 1;
  103. 				}
  104. 			}
  105.  
  106. 			output.append(count);
  107. 			output.append('\n');
  108. 		}
  109.  
  110. 		System.out.print(output);
  111.  
  112. 	} // end of main(String[])
  113.  
  114. }
  115.  
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin 
5 5
00000
00100
00010
10001
10000
3
2 2
1 1
3 2
stdout 
6
20
2
https://ideone.com/lvW7aq
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!