結果

問題 No.357 品物の並び替え (Middle)
ユーザー Grenache
提出日時 2016-04-02 18:54:36
言語 Java
(openjdk 23)
結果
AC  
実行時間 205 ms / 5,000 ms
コード長 1,202 bytes
コンパイル時間 3,552 ms
コンパイル使用メモリ 77,904 KB
実行使用メモリ 45,396 KB
最終ジャッジ日時 2024-10-02 12:29:39
合計ジャッジ時間 7,120 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.util.*;
public class Main_yukicoder357 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
List<List<Pair>> prev = new ArrayList<>();
for (int i = 0; i < n; i++) {
prev.add(new ArrayList<>());
}
for (int i = 0; i < m; i++) {
int item1 = sc.nextInt();
int item2 = sc.nextInt();
int score = sc.nextInt();
prev.get(item2).add(new Pair(item1, score));
}
int[] dp = new int[0x1 << n];
for (int i = 0; i < 0x1 << n; i++) {
for (int j = 0; j < n; j++) {
if ((i & 0x1 << j) != 0) {
continue;
}
int sum = 0;
for (Pair e : prev.get(j)) {
if ((i & 0x1 << e.a) != 0) {
sum += e.b;
}
}
dp[i | 0x1 << j] = Math.max(dp[i | 0x1 << j], dp[i] + sum);
}
}
System.out.println(dp[(0x1 << n) - 1]);
sc.close();
}
private static class Pair {
int a;
int b;
Pair(int a, int b) {
this.a = a;
this.b = b;
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0