結果
| 問題 | No.497 入れ子の箱 |
| ユーザー |
 jousen
|
| 提出日時 | 2017-03-25 00:25:08 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,658 bytes |
| コンパイル時間 | 2,305 ms |
| コンパイル使用メモリ | 94,792 KB |
| 実行使用メモリ | 74,588 KB |
| 最終ジャッジ日時 | 2024-07-06 03:17:47 |
| 合計ジャッジ時間 | 9,218 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 109 ms
46,408 KB |
| testcase_01 | AC | 101 ms
39,864 KB |
| testcase_02 | AC | 96 ms
39,780 KB |
| testcase_03 | TLE | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
ソースコード
package main;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import javax.imageio.stream.MemoryCacheImageInputStream;
public class Main {
private static int[] arr;
private int[][] ar2;
private List<Integer> list;
public static int n,m,k;
private static HashSet<Integer> set;
private static HashMap<Integer, Integer> map;
private static Scanner sc = new Scanner(System.in);
private static List<List<Integer>> ll;
private static List<HashSet<Integer>> hList;
private static boolean[] memo;
public static void main(String[] args){
//n = sc.nextInt();
//arr = new int[n];
n = sc.nextInt();
int[][] box = new int[n][3];
for(int i=0; i<n; i++){
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
box[i] = new int []{a,b,c};
}
memo= new boolean[n];
Arrays.sort(box,(a,b)->(a[0]*a[1]*a[2])-(b[0]*b[1]*b[2]));
int[][] dp = new int[n+1][n+1];
for(int i=0; i<n+1; i++){
dp[i] = new int[n+1];
for(int j=0; j<n+1; j++)
dp[i][j ]=1;
}
int mx = 1;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(i==j)continue;
boolean[][] ch = new boolean[3][3];
for(int l=0; l<3; l++){
ch[l] = new boolean[3];
int cur = box[i][l];
for(int r=0; r<3; r++){
int com = box[j][r];
if(cur<com)ch[l][r] = true;
}
}
if(check(ch)) dp[i][j]++;
mx = Math.max(mx, dp[i][j]);
}
}
for(int i=0; i<n; i++){
if(memo[i])continue;
memo[i] = true;
mx = Math.max(mx, dfs(i, box, n, 1));
}
// int count = 1;
// for(int i=0; i<n-1; i++){
// //int a = box[i];
// //int b = box[i+1];
// boolean[][] ch = new boolean[3][3];
// for(int l=0; l<3; l++){
// ch[l] = new boolean[3];
// int cur = box[i][l];
// for(int r=0; r<3; r++){
// int com = box[i+1][r];
// if(cur<com)ch[l][r] = true;
// }
// }
//
// boolean ok = check(ch);
//// for(int p=0; p<3; p++){
//// if(box[i][p]>=box[i+1][p])continue;
//// for(int j =0;j<3; j++){
//// if(j==p || box[i][j]>=box[i+1][j])continue;
//// for(int k=0; k<3; k++){
//// if(k==p || k==j || box[i][k]>=box[i+1][k])continue;
//// ok = true;
//// }
//// }
//// }
// if(ok)count++;
//
//
// }
System.out.println(mx);
}
public static boolean check(boolean[][] ch) {
for(int i=0; i<3; i++){
if(!ch[0][i])continue;
for(int j =0;j<3; j++){
if(j==i || !ch[1][j])continue;
for(int k=0; k<3; k++){
if(k==i || k==j || !ch[2][k])continue;
return true;
}
}
}
return false;
}
public static int dfs(int i, int[][] box, int n, int count) {
for(int j=i +1; j<n; j++){
//if(memo[j])continue;
boolean[][] ch = new boolean[3][3];
for(int l=0; l<3; l++){
ch[l] = new boolean[3];
int cur = box[i][l];
for(int r=0; r<3; r++){
int com = box[j][r];
if(cur<com)ch[l][r] = true;
}
}
if(check(ch)) {
count++;
memo[j]= true;
dfs(j, box, n, count);
}
}
return count;
}
}
class array2D{
public int[][] arr;
public array2D(int row, int col) {
arr = new int[row][col];
for(int i=0; i<row; i++){
arr[i] = new int[col];
for(int j=0; j<col; j++){
arr[i][j ]=0;
}
}
}
}
class Tupple{
int a=0, b=0;
public Tupple(int x, int y) {
// TODO 自動生成されたコンストラクター・スタブ
this.a = x;
this.b = y;
}
public int first() {
return this.a;
}
public int second() {
return this.b;
}
}
class sqrtArr{
public int[] arr;
public int n;
public sqrtArr(int x , int[] original) {
this.n = (int)Math.sqrt(x)+1;
arr = new int[n];
for(int i=0; i<x; i++){
arr[i/n] += original[i];
}
}
public int get(int l , int r) {
int sum =0;
for(int i=l; i<=r;){
if(i% n==0 && i+n-1 <=r){
sum += arr[i/n];
i += n;
}
else {
sum +=arr[i];
i++;
}
}
return sum;
}
}
class UnionFind{
public int[] path;
public int[] size;
public List<HashSet<Integer>> list;
public UnionFind (int n, int[] original) {
path = new int[n+1];
size = new int[n+1];
list = new ArrayList<HashSet<Integer>>();
for(int i=0; i<n; i++){
path[i] = i;
size[i] =1;
list.add(new HashSet<Integer>());
list.get(i).add(original[i]);
}
}
public int root(int i){
while (path[i] != i) {
path[i] = path[path[path[i]]];
i = path[i];
}
return i;
}
public boolean find(int p, int q) {
if(p<0 || q<0)return false;
return root(p) == root(q);
}
public void uniite(int p, int q) {
if(p<0 || q<0)return;
int i = root(p);
int j = root(q);
if(i==j)return;
if(size[i]>size[j]){
// int tmp = i;l
// i=j;
// j = tmp;
i^=j^=i^=j;
}
size[j ] += size[i];
path[i] = j;
}
}
class BIT{
int n;
private int[] bit = new int[100010];
public BIT(int x , int[] original){
this.n = x;
for(int i=1; i<=n; i++){
//bit[i] = original[i];
add(i, original[i]);
}
}
public void add(int a, int w) {
for(int i = a; i<=n; i+= i&(-i))bit[i] +=w;
}
public int sum(int a) {
int sum = 0;
for(int i=a;i>0; i-=i&(-i)) sum+=bit[i];
return sum;
}
public int binary(int w){
if(w<=0)return 0;
int x =0;
for(int k = n%2==0? n:n-1; k>0; k/=2){
if(x+k<=n && bit[x+k]<w){
w -=bit[x+k];
x += k;
}
}
return x+1;
}
}
class Segment{
int n;
int size ;
private int[] dat;
//private HashSet<Integer>[] dat;
public Segment(int x) {
this.n = x;
this.size = x*2;
dat = new int[size];
//dat = new HashSet<Integer>[size];
for(int i=0; i<size;i++){
dat[i] = Integer.MAX_VALUE;
//dat[i ] = new HashSet<>();
}
}
public void update(int i, int x) {
i = n+i-1;
dat[i ] = x;
while (i>0) {
i =(i-1)/2;
dat[i] = Math.min(dat[i*2+1], dat[i*2+2]);
}
}
int query(int a, int b, int k, int l, int r){
if(r<=a || b<=l)return Integer.MAX_VALUE;
if(a<=l && r<=b)return dat[k];
else {
int vl = query(a, b, k*2+1, l, (l+r)/2);
int vr = query(a, b, k*2+2, (l+r)/2, r);
return Math.min(vl, vr);
}
}
}
class Tree{
int n,l ;
private int[][] g;
private int[] tin,tout;
int timer;
private int[][] up;
public Tree(int n){
this.n = n;
tin = new int[n+1];
tout = new int[n+1];
timer = 0;
g= new int[n+1][l];
up = new int[n+1][l];
l = 1;
while ((1 << l) <= n) ++ l;
//for (int i = 0; i <n; ++ i) up [i] = new int[l+1];
for(int i=0; i<=n; i++){
g[i] = new int[l+1];
up[i]= new int[l+1];
}
}
void dfs (int v, int p) {
tin [v] = ++ timer;
up [v] [0] = p;
for (int i = 1; i <= l; ++ i)
up [v] [i] = up [up [v] [i-1]] [i-1];
for (int i = 0; i <g [v].length; ++ i) {
int to = g [v] [i];
if (to!= p)
dfs (to, v);
}
tout [v] = ++ timer;
}
boolean upper (int a, int b) {
return tin [a] <= tin [b] && tout [a]>= tout [b];
}
int lca (int a, int b) {
if (upper (a, b)) return a;
if (upper (b, a)) return b;
for (int i = l; i>= 0; --i)
if (! upper (up [a] [i], b))
a = up [a] [i];
return up [a] [0];
}
}
//class Tree{
// int n,l ;
// private int[][] g;
// private int[] tin,tout;
// int timer;
// private int[][] up;
// private int[] parent ;
//
// public Tree(int n){
// this.n = n;
// this.l = (int)Math.pow(2,n);
// tin = new int[n+1];
// tout = new int[n+1];
// timer = 0;
// parent = new int[n+1];
// g= new int[n+1][n+1];
// up = new int[n+1][n+1];
// for(int i=0; i<=n; i++){
// g[i] = new int[n+1];
// up[i]= new int[n+1];
// }
// }
//
// void preprocess(){
// //Every element in P[][] is -1 initially;
// for(int i = 1 ; i <= n ; ++i){
// for(int j = 0 ; (1<<j) < n ; ++i){
// g[i][j] = -1;
// }
// }
//
// //The first ancestor(2^0 th ancestor)
// //for every node is parent[node]
// for(int i = 1 ; i <= n ; ++i){
// g[i][0] = parent[i] ;
// }
//
// for(int j = 1; (1<<j) < n ; ++j){
// for(int i = 1 ; i <= n ; ++i){
// //If a node does not have a (2^(j-1))th ancestor
// //Then it does not have a (2^j)th ancestor
// //and hence P[i][j] should remain -1
// //Else the (2^j)th ancestor of node i
// //is the (2^(j-1))th ancestor of ((2^(j-1))th ancestor of node i)
// if(g[i][j-1] != -1){
// g[i][j] = g[g[i][j-1]][j-1] ;
// }
// }
// }
// }
// int LCA(int u , int v){
// if(level[u] < level[v]){
// swap(u,v) ;
// }
// //u is the node at a greater depth/lower level
// //So we have to raise u to be at the same
// //level as v.
// int dist = level[u] - level[v] ;
// while(dist > 0){
// int raise_by = log2(dist);
// u = P[u][raise_by];
// dist -= (1<<raise_by) ;
// }
//
// if(u == v){
// return u ;
// }
//
// //Now we keep raising the two nodes by equal amount
// //Untill each node has been raised uptill its (k-1)th ancestor
// //Such that the (k)th ancestor is the lca.
// //So to get the lca we just return the parent of (k-1)th ancestor
// //of each node
//
// for(int j = MAXLOG ; j >= 0 ; --j){
// //Checking P[u][j] != P[v][j] because if P[u][j] == P[v][j]
// //P[u][j] would be the Lth ancestor such that (L >= k)
// //where kth ancestor is the LCA
// //But we want the (k-1)th ancestor.
// if((P[u][j] != -1) and (P[u][j] != P[v][j])){
// u = P[u][j] ;
// v = P[v][j] ;
// }
// }
// return parent[u] ; //or parent[v]
// }
//}