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