結果
問題 | No.357 品物の並び替え (Middle) |
ユーザー |
|
提出日時 | 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 |
ソースコード
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;}}}