結果

問題 No.1045 直方体大学
ユーザー htensai
提出日時 2020-05-07 11:51:29
言語 Java
(openjdk 23)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

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