結果
問題 |
No.45 回転寿司
|
ユーザー |
|
提出日時 | 2016-08-01 14:30:38 |
言語 | Ruby (3.4.1) |
結果 |
AC
|
実行時間 | 124 ms / 5,000 ms |
コード長 | 1,175 bytes |
コンパイル時間 | 383 ms |
コンパイル使用メモリ | 7,168 KB |
実行使用メモリ | 12,672 KB |
最終ジャッジ日時 | 2024-12-27 14:57:30 |
合計ジャッジ時間 | 5,697 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
コンパイルメッセージ
Syntax OK
ソースコード
inputs = STDIN.readlines.map(&:chomp) N = inputs[0].to_i Vs = inputs[1].split(/\s+/).map(&:to_i) class Block def initialize(range, head_throughs, tail_throughs, max_value) @range = range @head_throughs = head_throughs @tail_throughs = tail_throughs @max_value = max_value end attr_reader :range, :head_throughs, :tail_throughs, :max_value end def merge(blocks1, blocks2) blocks1.product(blocks2).select { |block1, block2| throughs = block1.tail_throughs + block2.head_throughs 1 <= throughs && throughs <= 2 }.map { |block1, block2| Block.new( block1.range.first..block2.range.last, block1.head_throughs, block2.tail_throughs, block1.max_value + block2.max_value ) }.group_by { |block| [block.head_throughs, block.tail_throughs] }.map { |throughs, blocks| blocks.max_by(&:max_value) } end cands = Vs.map.with_index { |v, i| [Block.new(i..i, 0, 0, v), Block.new(i..i, 1, 1, 0)] } until cands.size == 1 cands = cands.each_slice(2).map { |blocks1, blocks2| if blocks2 merge(blocks1, blocks2) else blocks1 end } end puts cands.first.max_by(&:max_value).max_value