結果
問題 |
No.2686 商品券の使い道
|
ユーザー |
![]() |
提出日時 | 2024-03-20 22:40:37 |
言語 | Crystal (1.14.0) |
結果 |
AC
|
実行時間 | 47 ms / 3,000 ms |
コード長 | 624 bytes |
コンパイル時間 | 12,160 ms |
コンパイル使用メモリ | 294,880 KB |
実行使用メモリ | 19,380 KB |
最終ジャッジ日時 | 2024-09-30 08:45:13 |
合計ジャッジ時間 | 14,051 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 48 |
ソースコード
n, m, q = read_line.split.map(&.to_i) abs = Array.new(n) { read_line.split.map(&.to_i64) } sum_a = Array.new(1 << n, 0i64) sum_b = Array.new(1 << n, 0i64) 1.upto((1 << n) - 1) do |i| mi = i.trailing_zeros_count sum_a[i] = sum_a[i - (1 << mi)] + abs[mi][0] sum_b[i] = sum_b[i - (1 << mi)] + abs[mi][1] end ans = 0i64 (1 << n).times do |t| next if sum_a[t] > m + q next if sum_b[t] <= ans if sum_a[t] <= m || sum_a[t] <= q ans = {ans, sum_b[t]}.max end s = t while s > 0 s2 = t ^ s if sum_a[s] <= m && sum_a[s2] <= q ans = {ans, sum_b[t]}.max end s = (s - 1) & t end end puts ans