結果
問題 | No.324 落ちてた閉路グラフ |
ユーザー | 37zigen |
提出日時 | 2016-03-21 14:00:06 |
言語 | Java21 (openjdk 21) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,865 bytes |
コンパイル時間 | 2,653 ms |
コンパイル使用メモリ | 80,368 KB |
実行使用メモリ | 212,972 KB |
最終ジャッジ日時 | 2024-04-08 21:21:28 |
合計ジャッジ時間 | 16,420 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 161 ms
58,092 KB |
testcase_01 | AC | 152 ms
58,100 KB |
testcase_02 | AC | 153 ms
58,200 KB |
testcase_03 | AC | 152 ms
58,108 KB |
testcase_04 | AC | 650 ms
129,544 KB |
testcase_05 | AC | 873 ms
212,836 KB |
testcase_06 | WA | - |
testcase_07 | AC | 885 ms
212,972 KB |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | AC | 478 ms
76,960 KB |
testcase_12 | AC | 250 ms
60,968 KB |
testcase_13 | AC | 230 ms
60,820 KB |
testcase_14 | AC | 341 ms
69,876 KB |
testcase_15 | AC | 390 ms
81,672 KB |
testcase_16 | AC | 159 ms
57,996 KB |
testcase_17 | AC | 160 ms
58,352 KB |
testcase_18 | AC | 159 ms
58,088 KB |
testcase_19 | AC | 152 ms
58,092 KB |
testcase_20 | AC | 157 ms
58,204 KB |
testcase_21 | WA | - |
testcase_22 | AC | 156 ms
58,064 KB |
testcase_23 | WA | - |
testcase_24 | AC | 157 ms
58,324 KB |
testcase_25 | AC | 153 ms
58,212 KB |
testcase_26 | AC | 160 ms
57,832 KB |
testcase_27 | WA | - |
testcase_28 | AC | 156 ms
57,824 KB |
testcase_29 | WA | - |
testcase_30 | AC | 154 ms
58,096 KB |
testcase_31 | AC | 157 ms
57,836 KB |
testcase_32 | AC | 851 ms
212,516 KB |
testcase_33 | AC | 814 ms
212,068 KB |
testcase_34 | WA | - |
testcase_35 | AC | 178 ms
58,728 KB |
testcase_36 | WA | - |
testcase_37 | WA | - |
ソースコード
import java.util.Date; 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();//m頂点の誘導部分グラフ int[] w=new int[n]; for(int i=0;i<n;i++){ w[i]=sc.nextInt(); } long t=new Date().getTime(); int inf=-1000000; System.err.println(new Date().getTime()-t+"ms"); int[][][][] dp=new int[2][2][m+1][n+1]; System.err.println(new Date().getTime()-t+"ms"); //dp[0番目の頂点を拾ったかどうか0:拾わず/1:拾った][i番目まで確定][頂点数][i番目の頂点を拾ったか(0:拾わず/1:拾った)]=その時点での最大価値 for(int i=0;i<2;i++){//2*n*k*l=2*6*3*2=72 for(int l=0;l<2;l++){ for(int k=0;k<=m;k++){ for(int j=1;j<n;j++){ dp[i][l][k][j]=inf; } } } } System.err.println(new Date().getTime()-t+"ms"); for(int i=0;i<2;i++){ for(int j=1;j<=n;j++){ for(int k=0;k<=j&&k<=m;k++){ for(int l=0;l<2;l++){ if(k<l||k<i||(j!=n&&j+i-1+l-1<k)){ continue; }else if(l==0&&j>1){ dp[i][l][k][j]=Math.max(dp[i][0][k][j-1], dp[i][1][k][j-1]); }else if(l==1&&j>1){ dp[i][l][k][j]=Math.max(dp[i][0][k-1][j-1], dp[i][1][k-1][j-1]+w[j-2]); }else if(j==1){ dp[i][l][k][j]=0; }else{ System.err.println("Error dp["+i+"]["+l+"]["+k+"]["+j+"]="+dp[i][l][k][j]); } } } } } // for(int i=0;i<2;i++){ // for(int j=1;j<=n;j++){ // for(int k=0;k<=m;k++){ // for(int l=0;l<2;l++){ // System.err.println("dp["+i+"]["+l+"]["+k+"]["+j+"]="+dp[i][l][k][j]); // } // } // } // } int max; max=Math.max(dp[0][0][m][n],dp[0][1][m][n]); max=Math.max(dp[1][0][m][n],dp[1][1][m][n]+w[n-1]); System.out.println(max); System.err.println(new Date().getTime()-t+"ms"); } }