fork download
copy 
  1.  
  2.  
  3. import java.io.BufferedReader;
  4. import java.io.IOException;
  5. import java.io.InputStream;
  6. import java.io.InputStreamReader;
  7. import java.util.Arrays;
  8. import java.util.StringTokenizer;
  9.  
  10. public class Main {
  11.  
  12. 	public static int[][] grid;
  13. 	static int[][][] memo;
  14.  
  15. 	public static int solve(int r, int c, int max) {
  16. 		// System.out.println(r+" " + c);
  17. 		// System.out.println(grid.length);
  18. 		if (r == grid.length-1 && c == grid.length-1){
  19. //			System.out.println("jii");
  20. 			if(grid[r][c] > max)
  21. 				return 1;
  22. 			return 0;
  23. 		}
  24.  
  25. 		if (memo[r][c][max] != -1)
  26. 			return memo[r][c][max];
  27.  
  28. 		int rightTake = 0;
  29. 		int rightLeave = 0;
  30. 		if (r + 1 < grid.length && grid[r + 1][c] > max) {
  31. 			// System.out.println("hii");
  32. 			if (grid[r + 1][c] != -1)
  33. 				rightTake = 1 + solve(r + 1, c, Math.max(max, grid[r + 1][c]));
  34. 		}
  35. 		if (r + 1 < grid.length)
  36. 			rightLeave = solve(r + 1, c, max);
  37.  
  38. 		int leftTake = 0;
  39. 		int leftLeave = 0;
  40.  
  41. 		if (c + 1 < grid.length && grid[r][c + 1] > max) {
  42. 			// System.out.println("hi");
  43. 			if (grid[r][c + 1] != -1)
  44. 				leftTake = 1 + solve(r, c + 1, Math.max(max, grid[r][c + 1]));
  45. 			// else
  46. 			// left = solve(r, c+1);
  47. 		}
  48. 		if (c + 1 < grid.length)
  49. 			leftLeave = solve(r, c + 1, max);
  50. 		return memo[r][c][max] = Math.max(Math.max(leftTake, rightTake),
  51. 				Math.max(leftLeave, rightLeave));
  52.  
  53. 	}
  54.  
  55. 	public static void main(String[] args) throws IOException {
  56. 		Scanner sc = new Scanner(System.in);
  57. 		int n = sc.nextInt();
  58. 		grid = new int[n][n];
  59. 		for (int i = 0; i < grid.length; i++) {
  60. 			Arrays.fill(grid[i], -1);
  61. 		}
  62. 		int time = 1;
  63. 		for (int i = 0; i < n; i++) {
  64. 			int c = sc.nextInt() - 1;
  65. 			int r = sc.nextInt() - 1;
  66. 			grid[r][c] = time;
  67. 			time++;
  68. 		}
  69. 		memo = new int[n + 1][n + 1][time + 10];
  70. 		for (int i = 0; i < memo.length; i++) {
  71. 			for (int j = 0; j < memo[i].length; j++) {
  72. 				Arrays.fill(memo[i][j], -1);
  73. 			}
  74. 		}
  75. 		// for (int i = 0; i < grid.length; i++) {
  76. 		// System.out.println(Arrays.toString(grid[i]));
  77. 		// }
  78. 		int one = solve(0, 0, 0);
  79. 		int two = 0;
  80. 		if (grid[0][0] != -1)
  81. 			two = 1 + solve(0, 0, grid[0][0]);
  82.  
  83. 		System.out.println(Math.max(one, two));
  84.  
  85. 	}
  86.  
  87. 	static class Scanner {
  88. 		StringTokenizer st;
  89. 		BufferedReader br;
  90.  
  91. 		public Scanner(InputStream s) {
  92. 			br = new BufferedReader(new InputStreamReader(s));
  93. 		}
  94.  
  95. 		public String next() throws IOException {
  96. 			while (st == null || !st.hasMoreTokens())
  97. 				st = new StringTokenizer(br.readLine());
  98. 			return st.nextToken();
  99. 		}
  100.  
  101. 		public int nextInt() throws IOException {
  102. 			return Integer.parseInt(next());
  103. 		}
  104.  
  105. 		public long nextLong() throws IOException {
  106. 			return Long.parseLong(next());
  107. 		}
  108.  
  109. 		public String nextLine() throws IOException {
  110. 			return br.readLine();
  111. 		}
  112.  
  113. 		public double nextDouble() throws IOException {
  114. 			String x = next();
  115. 			StringBuilder sb = new StringBuilder("0");
  116. 			double res = 0, f = 1;
  117. 			boolean dec = false, neg = false;
  118. 			int start = 0;
  119. 			if (x.charAt(0) == '-') {
  120. 				neg = true;
  121. 				start++;
  122. 			}
  123. 			for (int i = start; i < x.length(); i++)
  124. 				if (x.charAt(i) == '.') {
  125. 					res = Long.parseLong(sb.toString());
  126. 					sb = new StringBuilder("0");
  127. 					dec = true;
  128. 				} else {
  129. 					sb.append(x.charAt(i));
  130. 					if (dec)
  131. 						f *= 10;
  132. 				}
  133. 			res += Long.parseLong(sb.toString()) / f;
  134. 			return res * (neg ? -1 : 1);
  135. 		}
  136.  
  137. 		public boolean ready() throws IOException {
  138. 			return br.ready();
  139. 		}
  140.  
  141. 	}
  142. }
Runtime error #stdin #stdout #stderr 0.04s 320576KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" java.lang.NullPointerException
	at java.util.StringTokenizer.<init>(StringTokenizer.java:199)
	at java.util.StringTokenizer.<init>(StringTokenizer.java:236)
	at Main$Scanner.next(Main.java:97)
	at Main$Scanner.nextInt(Main.java:102)
	at Main.main(Main.java:57)
https://ideone.com/Op3DVt
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
public

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!