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