結果
問題 | No.497 入れ子の箱 |
ユーザー |
![]() |
提出日時 | 2021-11-12 08:47:41 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 163 ms / 5,000 ms |
コード長 | 2,861 bytes |
コンパイル時間 | 2,797 ms |
コンパイル使用メモリ | 78,228 KB |
実行使用メモリ | 47,400 KB |
最終ジャッジ日時 | 2024-11-24 14:43:55 |
合計ジャッジ時間 | 8,556 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
import java.util.*;import java.io.*;public class Main {static Box[] boxes;static int[][] dp;public static void main(String[] args) throws Exception {Scanner sc = new Scanner();int n = sc.nextInt();boxes = new Box[n + 1];for (int i = 0; i < n; i++) {boxes[i] = new Box(sc.nextInt(), sc.nextInt(), sc.nextInt());}boxes[n] = new Box(Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE);Arrays.sort(boxes);dp = new int[n + 1][n + 1];for (int[] arr : dp) {Arrays.fill(arr, -1);}System.out.println(dfw(n - 1, n));}static int dfw(int idx, int prev) {if (idx < 0) {return 0;}if (dp[idx][prev] < 0) {dp[idx][prev] = dfw(idx - 1, prev);if (boxes[idx].x < boxes[prev].x && boxes[idx].y < boxes[prev].y && boxes[idx].z < boxes[prev].z) {dp[idx][prev] = Math.max(dp[idx][prev], dfw(idx - 1, idx) + 1);}}return dp[idx][prev];}static class Box implements Comparable<Box> {int x;int y;int z;public Box(int x, int y, int z) {this.x = x;this.y = y;this.z = z;sort();}private void sort() {if (y > z) {int tmp = z;z = y;y = tmp;}if (x > y) {int tmp = y;y = x;x = tmp;}if (y > z) {int tmp = z;z = y;y = tmp;}}public int compareTo(Box another) {if (x == another.x) {if (y == another.y) {return z - another.z;} else {return y - another.y;}} else {return x - another.x;}}}}class Scanner {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StringTokenizer st = new StringTokenizer("");public Scanner() throws Exception {}public int nextInt() throws Exception {return Integer.parseInt(next());}public long nextLong() throws Exception {return Long.parseLong(next());}public double nextDouble() throws Exception {return Double.parseDouble(next());}public String nextLine() throws Exception {return br.readLine();}public String next() throws Exception {if (!st.hasMoreTokens()) {st = new StringTokenizer(br.readLine());}return st.nextToken();}}