結果
問題 | No.324 落ちてた閉路グラフ |
ユーザー |
|
提出日時 | 2017-01-19 15:39:33 |
言語 | Crystal (1.14.0) |
結果 |
AC
|
実行時間 | 258 ms / 5,000 ms |
コード長 | 528 bytes |
コンパイル時間 | 11,600 ms |
コンパイル使用メモリ | 295,908 KB |
実行使用メモリ | 159,948 KB |
最終ジャッジ日時 | 2024-06-30 19:11:17 |
合計ジャッジ時間 | 16,423 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 34 |
ソースコード
#!/usr/bin/env crystalMIN=-100000000Memo=Array(Int32).new(40000000,MIN)def dfs(n,w,z,prev,cur,remain)key=z*20000000+prev*10000000+cur*3100+remainif remain<0 || remain>n-curMINelsif cur==nw[cur-1]*prev*zelsif Memo[key]!=MINMemo[key]elser1=dfs(n,w,z,0,cur+1,remain)r2=dfs(n,w,z,1,cur+1,remain-1)+w[cur-1]*prevMemo[key] = r1>r2 ? r1 : r2endendn,m=gets.not_nil!.split.map(&.to_i)w=gets.not_nil!.split.map(&.to_i)if m<2p 0elser1=dfs(n,w,0,0,1,m)r2=dfs(n,w,1,1,1,m-1)p r1>r2 ? r1 : r2end