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