結果

問題 No.1045 直方体大学
ユーザー htensaihtensai
提出日時 2020-05-07 11:51:29
言語 Java21
(openjdk 21)
結果
AC  
実行時間 1,428 ms / 2,000 ms
コード長 2,142 bytes
コンパイル時間 2,578 ms
コンパイル使用メモリ 82,960 KB
実行使用メモリ 225,036 KB
最終ジャッジ日時 2023-09-16 07:51:13
合計ジャッジ時間 14,600 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 129 ms
55,676 KB
testcase_01 AC 126 ms
55,768 KB
testcase_02 AC 131 ms
55,872 KB
testcase_03 AC 134 ms
55,600 KB
testcase_04 AC 133 ms
55,928 KB
testcase_05 AC 172 ms
60,196 KB
testcase_06 AC 174 ms
58,440 KB
testcase_07 AC 174 ms
58,296 KB
testcase_08 AC 888 ms
125,260 KB
testcase_09 AC 957 ms
128,344 KB
testcase_10 AC 352 ms
85,796 KB
testcase_11 AC 852 ms
124,140 KB
testcase_12 AC 1,008 ms
162,288 KB
testcase_13 AC 1,428 ms
225,036 KB
testcase_14 AC 977 ms
169,284 KB
testcase_15 AC 1,309 ms
174,660 KB
testcase_16 AC 979 ms
149,528 KB
testcase_17 AC 137 ms
55,868 KB
testcase_18 AC 976 ms
172,768 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