結果
問題 | No.357 品物の並び替え (Middle) |
ユーザー | ぴろず |
提出日時 | 2016-04-15 16:25:13 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 2,003 ms / 5,000 ms |
コード長 | 1,681 bytes |
コンパイル時間 | 1,976 ms |
コンパイル使用メモリ | 79,092 KB |
実行使用メモリ | 55,248 KB |
最終ジャッジ日時 | 2024-10-04 09:27:44 |
合計ジャッジ時間 | 9,299 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 130 ms
54,120 KB |
testcase_01 | AC | 113 ms
52,852 KB |
testcase_02 | AC | 112 ms
53,124 KB |
testcase_03 | AC | 131 ms
53,840 KB |
testcase_04 | AC | 134 ms
54,116 KB |
testcase_05 | AC | 134 ms
54,236 KB |
testcase_06 | AC | 131 ms
54,268 KB |
testcase_07 | AC | 121 ms
53,884 KB |
testcase_08 | AC | 147 ms
54,356 KB |
testcase_09 | AC | 707 ms
55,036 KB |
testcase_10 | AC | 216 ms
55,148 KB |
testcase_11 | AC | 240 ms
55,156 KB |
testcase_12 | AC | 2,003 ms
55,132 KB |
testcase_13 | AC | 726 ms
55,016 KB |
testcase_14 | AC | 708 ms
54,976 KB |
testcase_15 | AC | 229 ms
55,060 KB |
testcase_16 | AC | 269 ms
55,064 KB |
testcase_17 | AC | 242 ms
55,248 KB |
ソースコード
package no357; import java.util.ArrayList; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int[][] score = new int[n][n]; for(int i=0;i<m;i++) { int it1 = sc.nextInt(); int it2 = sc.nextInt(); score[it1][it2] = sc.nextInt(); } int n1 = n / 2; int max = 0; for(int i=0;i<1<<n;i++) { if (Integer.bitCount(i) != n1) { continue; } int sum = 0; for(int j=0;j<n;j++) { if ((i >> j & 1) == 1) continue; for(int k=0;k<n;k++) { if ((i >> k & 1) == 0) continue; sum += score[j][k]; } } int max1 = max(n,i,0,score); int max2 = max(n,i,1,score); max = Math.max(max, sum + max1 + max2); } System.out.println(max); } static int max(int n,int mask,int use,int[][] score) { ArrayList<Integer> al = new ArrayList<>(); for(int i=0;i<n;i++) { if ((mask >> i & 1) == use) { al.add(i); } } int n1 = al.size(); int[] p = new int[n1]; for(int i=0;i<n1;i++) { p[i] = al.get(i); } int max = 0; do { int sum = 0; for(int i=0;i<n1;i++) { for(int j=i+1;j<n1;j++) { sum += score[p[i]][p[j]]; } } max = Math.max(sum,max); } while(nextPermutation(p)); return max; } static boolean nextPermutation(int[] p) { for(int a=p.length-2;a>=0;--a) { if(p[a]<p[a+1]) { for(int b=p.length-1;;--b) { if(p[b]>p[a]) { int t = p[a]; p[a] = p[b]; p[b] = t; for(++a, b=p.length-1;a<b;++a,--b) { t = p[a]; p[a] = p[b]; p[b] = t; } return true; } } } } return false; } }