結果
問題 | No.90 品物の並び替え |
ユーザー | Grenache |
提出日時 | 2015-07-01 17:53:19 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 274 ms / 5,000 ms |
コード長 | 1,552 bytes |
コンパイル時間 | 4,503 ms |
コンパイル使用メモリ | 75,216 KB |
実行使用メモリ | 59,332 KB |
最終ジャッジ日時 | 2023-09-22 04:58:43 |
合計ジャッジ時間 | 6,264 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 120 ms
55,716 KB |
testcase_01 | AC | 168 ms
59,332 KB |
testcase_02 | AC | 117 ms
56,348 KB |
testcase_03 | AC | 154 ms
56,904 KB |
testcase_04 | AC | 158 ms
56,912 KB |
testcase_05 | AC | 175 ms
59,184 KB |
testcase_06 | AC | 163 ms
58,976 KB |
testcase_07 | AC | 153 ms
56,296 KB |
testcase_08 | AC | 121 ms
55,344 KB |
testcase_09 | AC | 274 ms
59,152 KB |
ソースコード
import java.util.Scanner; public class Main_yukicoder90 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); item1 = new int[m]; item2 = new int[m]; score = new int[m]; for (int i = 0; i < m; i++) { item1[i] = sc.nextInt(); item2[i] = sc.nextInt(); score[i] = sc.nextInt(); } max = 0; used = new boolean[n]; perm = new int[n]; permutation(0, n); System.out.println(max); sc.close(); } private static int[] item1; private static int[] item2; private static int[] score; private static int max; private static boolean[] used; private static int[] perm; // {0, 1, 2, 3, ...., n - 1}の並び替えn!通りを生成する private static void permutation(int pos, int n) { if (pos == n) { // perm[] に対する操作 int[] index = new int[n]; for (int i = 0; i < n; i++) { index[perm[i]] = i; } int sc = 0; for (int i = 0; i < item1.length; i++) { if (index[item1[i]] < index[item2[i]]) { sc += score[i]; } } max = Math.max(max, sc); return; } // perm[]のpos番目を0~n-1のどれにするかのループ for (int i = 0; i < n; i++) { if (!used[i]) { perm[pos] = i; // iを使ったのでフラグをtrue used[i] = true; permutation(pos + 1, n); // 戻ってきたらフラグを戻す used[i] = false; } } return; } }