fork download 
  1. /* paiza POH! vol.2
  2.  * result:
  3.  * http://p...content-available-to-author-only...a.jp/poh/paizen/result/4c956b9cc53487fa61f4e9bc74440894
  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. 		Paiza.getInstance().resolve(new MyResolver());
  15. 	}
  16. }
  17.  
  18. class MyResolver extends Paiza.Resolver
  19. {
  20. 	private int[][] space2right = null;
  21. 	private int[][] space2bottom = null;
  22. 	private int[][] result = null;
  23.  
  24. 	@Override
  25. 	public void setHome(Paiza.Home home) {
  26. 		super.setHome(home);
  27.  
  28. 		space2right = new int[home.getH()][home.getW()];
  29. 		int allSpaceCount = 0;
  30.  
  31. 		for (int y = 0; y < home.getH(); y++) {
  32. 			int count = 0;
  33. 			for (int x = home.getW() - 1; x >= 0; x--) {
  34. 				if (home.isSpace(x, y)) {
  35. 					count++;
  36. 					allSpaceCount++;
  37. 				} else {
  38. 					count = 0;
  39. 				}
  40. 				space2right[y][x] = count;
  41. 			}
  42. 		}
  43.  
  44. 		space2bottom = new int[home.getH()][home.getW()];
  45.  
  46. 		for (int x = 0; x < home.getW(); x++) {
  47. 			int count = 0;
  48. 			for (int y = home.getH() - 1; y >= 0; y--) {
  49. 				if (home.isSpace(x, y)) {
  50. 					count++;
  51. 				} else {
  52. 					count = 0;
  53. 				}
  54. 				space2bottom[y][x] = count;
  55. 			}
  56. 		}
  57.  
  58. 		result = new int[301][301];
  59. 		result[1][1] = allSpaceCount + 1;
  60.  
  61. 	}
  62.  
  63. 	@Override
  64. 	public int resolve(Paiza.Widget widget) {
  65. 		if (result[widget.getS()][widget.getT()] > 0) {
  66. 			return result[widget.getS()][widget.getT()] - 1;
  67. 		}
  68. 		int count;
  69. 		if (widget.getS() > home.getH() || widget.getT() > home.getW()) {
  70. 			count = 0;
  71. 		} else if (widget.getS() > widget.getT()) {
  72. 			if (widget.getT() != 1) {
  73. 				count = resolve2bottom(widget);
  74. 			} else {
  75. 				count = resolveVBar(widget);
  76. 			}
  77. 		} else {
  78. 			if (widget.getS() != 1) {
  79. 				count = resolve2right(widget);
  80. 			} else {
  81. 				count = resolveHBar(widget);
  82. 			}
  83. 		}
  84. 		result[widget.getS()][widget.getT()] = count + 1;
  85. 		return count;
  86. 	}
  87.  
  88. 	private int resolve2right(Paiza.Widget widget) {
  89. 		int count = 0;
  90. 		for (int y = 0; y <= home.getH() - widget.getS(); y++) {
  91. 			for (int x = 0; x <= home.getW() - widget.getT(); x++) {
  92. 				if (space2bottom[y][x] >= widget.getS()) {
  93. 					boolean placeable = true;
  94. 					for (int dy = 0; placeable && dy < widget.getS(); dy++) {
  95. 						if (space2right[y + dy][x] < widget.getT()) {
  96. 							placeable = false;
  97. 							x += space2right[y + dy][x];
  98. 						}
  99. 					}
  100. 					if (placeable) {
  101. 						count++;
  102. 					}
  103. 				} else if (space2right[y][x] < widget.getT()) {
  104. 					x += space2right[y][x];
  105. 				}
  106. 			}
  107. 		}
  108. 		return count;
  109. 	}
  110.  
  111. 	private int resolve2bottom(Paiza.Widget widget) {
  112. 		int count = 0;
  113. 		for (int x = 0; x <= home.getW() - widget.getT(); x++) {
  114. 			for (int y = 0; y <= home.getH() - widget.getS(); y++) {
  115. 				if (space2right[y][x] >= widget.getT()) {
  116. 					boolean placeable = true;
  117. 					for (int dx = 0; placeable && dx < widget.getT(); dx++) {
  118. 						if (space2bottom[y][x + dx] < widget.getS()) {
  119. 							placeable = false;
  120. 							y += space2bottom[y][x + dx];
  121. 						}
  122. 					}
  123. 					if (placeable) {
  124. 						count++;
  125. 					}
  126. 				} else if (space2bottom[y][x] < widget.getS()) {
  127. 					y += space2bottom[y][x];
  128. 				}
  129. 			}
  130. 		}
  131. 		return count;
  132. 	}
  133.  
  134. 	private int resolveHBar(Paiza.Widget widget) {
  135. 		int count = 0;
  136. 		for (int y = 0; y <= home.getH() - widget.getS(); y++) {
  137. 			for (int x = 0; x <= home.getW() - widget.getT(); x++) {
  138. 				int len = space2right[y][x];
  139. 				if (len >= widget.getT()) {
  140. 					count += len - widget.getT() + 1;
  141. 				}
  142. 				x += len;
  143. 			}
  144. 		}
  145. 		return count;
  146. 	}
  147.  
  148. 	private int resolveVBar(Paiza.Widget widget) {
  149. 		int count = 0;
  150. 		for (int x = 0; x <= home.getW() - widget.getT(); x++) {
  151. 			for (int y = 0; y <= home.getH() - widget.getS(); y++) {
  152. 				int len = space2bottom[y][x];
  153. 				if (len >= widget.getS()) {
  154. 					count += len - widget.getS() + 1;
  155. 				}
  156. 				y += len;
  157. 			}
  158. 		}
  159. 		return count;
  160. 	}
  161.  
  162. }
  163.  
  164.  
  165. abstract class Resolver
  166. {
  167. 	protected Paiza.Home home;
  168.  
  169. 	public void setHome(Paiza.Home home) {
  170. 		this.home = home;
  171. 	}
  172.  
  173. 	public abstract int resolve(Paiza.Widget widget);
  174. }
  175.  
  176. final class Paiza
  177. {
  178. 	public static abstract class Resolver
  179. 	{
  180. 		protected Paiza.Home home;
  181.  
  182. 		public void setHome(Paiza.Home home) {
  183. 			this.home = home;
  184. 		}
  185.  
  186. 		public abstract int resolve(Paiza.Widget widget);
  187. 	}
  188.  
  189. 	public static Paiza getInstance() throws java.lang.Exception {
  190. 		if (paiza == null) {
  191. 			paiza = new Paiza();
  192. 		}
  193. 		return paiza;
  194. 	}	
  195.  
  196. 	public void resolve(Resolver resolver) {
  197. 		init(resolver);
  198. 		for (Widget widget : widgets) {
  199. 			answer(resolver.resolve(widget));
  200. 		}
  201. 		flush();
  202. 	}
  203.  
  204.  
  205. 	public final class Home
  206. 	{
  207. 		private final int H;
  208. 		private final int W;
  209. 		private int[][] display;
  210. 		private Home(int H, int W) {
  211. 			this.H = H;
  212. 			this.W = W;
  213. 			display = new int[H][W];
  214. 		}
  215.  
  216. 		private void setDisplay(int x, int y, int e) throws java.lang.Exception {
  217. 			if (x < 0 || x >= W) {
  218. 				throw new ArrayIndexOutOfBoundsException("x : " + x);
  219. 			}
  220. 			if (y < 0 || y >= H) {
  221. 				throw new ArrayIndexOutOfBoundsException("y : " + y);
  222. 			}
  223. 			if (e != 0 && e != 1) {
  224. 				throw new IllegalArgumentException("e");
  225. 			}
  226. 			display[y][x] = e;
  227. 		}
  228.  
  229. 		public int getH() {
  230. 			return H;
  231. 		}
  232.  
  233. 		public int getW() {
  234. 			return W;
  235. 		}
  236.  
  237. 		public boolean isSpace(int x, int y) {
  238. 			if (x < 0 || y < 0 || x >= W || y >= H) {
  239. 				return false;
  240. 			}
  241. 			return display[y][x] == 0;
  242. 		}
  243. 	}
  244.  
  245. 	public final class Widget
  246. 	{
  247. 		private final int s;
  248. 		private final int t;
  249. 		private Widget(int s, int t) {
  250. 			this.s = s;
  251. 			this.t = t;
  252. 		}
  253.  
  254. 		public int getS() {
  255. 			return s;
  256. 		}
  257.  
  258. 		public int getT() {
  259. 			return t;
  260. 		}
  261. 	}
  262.  
  263. 	private static Paiza paiza = null;
  264.  
  265. 	private Home home;
  266. 	private ArrayList<Widget> widgets;
  267.  
  268. 	private Paiza() throws java.lang.Exception {
  269. 		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  270. 		String[] hw = in.readLine().split(" ");
  271. 		home = new Home(Integer.parseInt(hw[0]), Integer.parseInt(hw[1]));
  272. 		for (int y = 0; y < home.getH(); y++) {
  273. 			String line = in.readLine();
  274. 			for (int x = 0; x < home.getW(); x++) {
  275. 				home.setDisplay(x, y, (int)(line.charAt(x) - '0'));
  276. 			}
  277. 		}
  278. 		int N = Integer.parseInt(in.readLine());
  279. 		widgets = new ArrayList<Widget>(N);
  280. 		for (int i = 0; i< N; i++) {
  281. 			String[] st = in.readLine().split(" ");
  282. 			widgets.add(new Widget(Integer.parseInt(st[0]), Integer.parseInt(st[1])));
  283. 		}
  284. 	}
  285.  
  286. 	private StringBuilder output = null;
  287. 	private static final String NEWLINE = System.getProperty("line.separator");
  288.  
  289. 	private void init(Resolver resolver) {
  290. 		resolver.setHome(home);
  291. 		output = new StringBuilder(widgets.size() * 6);
  292. 	}
  293.  
  294. 	private void answer(int count) {
  295. 		output.append(count);
  296. 		output.append(NEWLINE);
  297. 	}
  298.  
  299. 	private void flush() {
  300. 		System.out.print(output);
  301. 	}
  302. }
  303.  
Success #stdin #stdout 0.08s 380160KB
comments (?)
stdin 
5 5
00000
00100
00010
10001
10000
3
2 2
1 1
3 2
stdout 
6
20
2
https://ideone.com/y4oUSV
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!