結果
問題 | No.2389 Cheating Code Golf |
ユーザー | 👑 Mizar |
提出日時 | 2023-07-17 17:04:18 |
言語 | Ruby (3.3.0) |
結果 |
AC
|
実行時間 | 903 ms / 2,000 ms |
コード長 | 762 bytes |
コンパイル時間 | 483 ms |
コンパイル使用メモリ | 11,768 KB |
実行使用メモリ | 17,460 KB |
最終ジャッジ日時 | 2023-10-18 00:28:41 |
合計ジャッジ時間 | 12,367 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 85 ms
15,976 KB |
testcase_01 | AC | 85 ms
15,972 KB |
testcase_02 | AC | 262 ms
17,224 KB |
testcase_03 | AC | 903 ms
17,460 KB |
testcase_04 | AC | 902 ms
17,460 KB |
testcase_05 | AC | 102 ms
16,272 KB |
testcase_06 | AC | 84 ms
17,028 KB |
testcase_07 | AC | 116 ms
16,204 KB |
testcase_08 | AC | 328 ms
16,936 KB |
testcase_09 | AC | 85 ms
16,764 KB |
testcase_10 | AC | 89 ms
17,292 KB |
testcase_11 | AC | 119 ms
16,536 KB |
testcase_12 | AC | 86 ms
16,236 KB |
testcase_13 | AC | 265 ms
17,228 KB |
testcase_14 | AC | 141 ms
16,444 KB |
testcase_15 | AC | 89 ms
16,236 KB |
testcase_16 | AC | 283 ms
16,672 KB |
testcase_17 | AC | 86 ms
15,980 KB |
testcase_18 | AC | 124 ms
16,440 KB |
testcase_19 | AC | 86 ms
15,980 KB |
testcase_20 | AC | 88 ms
16,236 KB |
testcase_21 | AC | 101 ms
16,468 KB |
testcase_22 | AC | 89 ms
16,236 KB |
testcase_23 | AC | 89 ms
16,236 KB |
testcase_24 | AC | 112 ms
16,232 KB |
testcase_25 | AC | 102 ms
16,468 KB |
testcase_26 | AC | 88 ms
16,812 KB |
testcase_27 | AC | 150 ms
16,148 KB |
testcase_28 | AC | 110 ms
16,232 KB |
testcase_29 | AC | 89 ms
17,068 KB |
testcase_30 | AC | 230 ms
17,200 KB |
testcase_31 | AC | 94 ms
16,276 KB |
testcase_32 | AC | 84 ms
15,976 KB |
testcase_33 | AC | 84 ms
16,236 KB |
testcase_34 | AC | 167 ms
16,148 KB |
testcase_35 | AC | 100 ms
16,276 KB |
testcase_36 | AC | 233 ms
17,208 KB |
testcase_37 | AC | 90 ms
17,292 KB |
testcase_38 | AC | 420 ms
17,200 KB |
testcase_39 | AC | 86 ms
17,292 KB |
testcase_40 | AC | 89 ms
17,028 KB |
testcase_41 | AC | 92 ms
16,148 KB |
testcase_42 | AC | 91 ms
16,236 KB |
testcase_43 | AC | 86 ms
16,236 KB |
testcase_44 | AC | 88 ms
17,292 KB |
testcase_45 | AC | 389 ms
16,460 KB |
testcase_46 | AC | 230 ms
16,204 KB |
testcase_47 | AC | 85 ms
16,236 KB |
testcase_48 | AC | 112 ms
16,328 KB |
testcase_49 | AC | 138 ms
16,440 KB |
testcase_50 | AC | 84 ms
16,236 KB |
testcase_51 | AC | 118 ms
16,536 KB |
testcase_52 | AC | 102 ms
16,276 KB |
コンパイルメッセージ
Syntax OK
ソースコード
n, m = gets.split.map(&:to_i) iabpp = (1..n).map{ a, b, p = gets.split.map(&:to_f) [1.0 / a, 1.0 / b, 1.0 / p, 1.0 - 1.0 / p] } dp = Array.new(4096, -Float::INFINITY) full_bit = (1 << n) - 1 (0..m).each do dpc = dp.dup dpc[0] = 0.0 (1..n).each do |i| bidx = (1 << i) - 1 while bidx <= full_bit do point = 0.0 pit = bidx while pit > 0 do pbit = pit & -pit pidx = (pbit - 1).bit_length dpidx = bidx ^ pbit (af, bf, psucc, pfail) = iabpp[pidx] point = [point, dpc[dpidx] + af, (dpc[dpidx] + bf) * psucc + dp[bidx] * pfail].filter(&:finite?).max pit &= pit - 1 end dpc[bidx] = [dpc[bidx], point].max x = bidx & -bidx y = bidx + x bidx = ((bidx & ~y) / x >> 1) | y end end dp = dpc end puts dp[full_bit]