結果

問題 No.1045 直方体大学
ユーザー htensaihtensai
提出日時 2020-05-07 11:51:29
言語 Java21
(openjdk 21)
結果
AC  
実行時間 1,384 ms / 2,000 ms
コード長 2,142 bytes
コンパイル時間 2,568 ms
コンパイル使用メモリ 85,288 KB
実行使用メモリ 230,332 KB
最終ジャッジ日時 2024-07-03 09:23:26
合計ジャッジ時間 13,503 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 120 ms
41,124 KB
testcase_01 AC 114 ms
41,276 KB
testcase_02 AC 125 ms
41,384 KB
testcase_03 AC 107 ms
40,876 KB
testcase_04 AC 120 ms
41,488 KB
testcase_05 AC 145 ms
43,844 KB
testcase_06 AC 149 ms
43,600 KB
testcase_07 AC 144 ms
43,788 KB
testcase_08 AC 806 ms
114,904 KB
testcase_09 AC 908 ms
119,480 KB
testcase_10 AC 311 ms
72,740 KB
testcase_11 AC 868 ms
115,092 KB
testcase_12 AC 962 ms
161,080 KB
testcase_13 AC 1,384 ms
230,332 KB
testcase_14 AC 942 ms
164,524 KB
testcase_15 AC 1,216 ms
172,748 KB
testcase_16 AC 972 ms
151,480 KB
testcase_17 AC 124 ms
41,652 KB
testcase_18 AC 906 ms
160,876 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		Box[] boxes = new Box[n * 3];
		for (int i = 0; i < n; i++) {
		    int a = sc.nextInt();
		    int b = sc.nextInt();
		    int c = sc.nextInt();
		    boxes[i * 3] = new Box(i, a, b, c);
		    boxes[i * 3 + 1] = new Box(i, b, a, c);
		    boxes[i * 3 + 2] = new Box(i, c, a, b);
		}
		Arrays.sort(boxes);
		ArrayList<HashMap<Integer, HashMap<Integer, Integer>>> dp = new ArrayList<>();
		for (int i = 0; i < n * 3; i++) {
		    dp.add(new HashMap<>());
		}
		System.out.println(dfw(n * 3 - 1, dp, boxes, 0, Integer.MAX_VALUE));
	}
	
	static int dfw(int idx, ArrayList<HashMap<Integer, HashMap<Integer, Integer>>> dp, Box[] boxes, int used, int horizontal) {
	    if (idx < 0) {
	        return 0;
	    }
	    if (dp.get(idx).containsKey(used)) {
	        if (dp.get(idx).get(used).containsKey(horizontal)) {
	            return dp.get(idx).get(used).get(horizontal);
	        }
	    }
	    int max = dfw(idx - 1, dp, boxes, used, horizontal);
	    if (boxes[idx].horizontal <= horizontal && (used & (1 << boxes[idx].idx)) == 0) {
	        max = Math.max(max, dfw(idx - 1, dp, boxes, used ^ (1 << boxes[idx].idx), boxes[idx].horizontal) + boxes[idx].height);
	    }
	    if (!dp.get(idx).containsKey(used)) {
	        dp.get(idx).put(used, new HashMap<>());
	    }
	    dp.get(idx).get(used).put(horizontal, max);
	    return max;
	}
	
	static class Box implements Comparable<Box> {
	    int idx;
	    int height;
	    int horizontal;
	    int vertical;
	    
	    public Box(int idx, int a, int b, int c) {
	        this.idx = idx;
	        height = a;
            vertical = Math.min(b, c);
            horizontal = Math.max(b, c);
	    }
	    
	    public int compareTo(Box another) {
	        if (vertical == another.vertical) {
	            return horizontal - another.horizontal;
	        } else {
	            return vertical - another.vertical;
	        }
	    }
	    
	    public String toString() {
	        return idx + ":" + height + ":" + vertical + ":" + horizontal;
	    }
	}
}
0