結果

問題 No.9 モンスターのレベル上げ
ユーザー vjudge1
提出日時 2025-09-05 09:15:53
言語 Crystal
(1.14.0)
結果
WA  
実行時間 -
コード長 1,043 bytes
コンパイル時間 12,935 ms
コンパイル使用メモリ 308,704 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-09-05 09:16:25
合計ジャッジ時間 30,305 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 10 WA * 2 TLE * 1 -- * 7
権限があれば一括ダウンロードができます

ソースコード

diff #

record Node, value : Int32, depth : Int32

n = gets.not_nil!.to_i
a = gets.not_nil!.split.map(&.to_i)
b = gets.not_nil!.split.map(&.to_i)

ans = n

n.times do |start|
  # Create min-heap using array (we'll manually maintain it)
  heap = a.map { |val| Node.new(val, 0) }
  max_depth = 0
  valid = true
  
  n.times do |j|
    # Find the node with minimum value
    min_index = 0
    heap.each_with_index do |node, idx|
      if node.value < heap[min_index].value
        min_index = idx
      end
    end
    
    # Remove the min node
    min_node = heap.delete_at(min_index)
    
    # Calculate new value and depth
    new_value = min_node.value + b[(start + j) % n] // 2
    new_depth = min_node.depth + 1
    
    max_depth = Math.max(max_depth, new_depth)
    
    # Early termination if we can't beat current best answer
    if max_depth >= ans
      valid = false
      break
    end
    
    # Add the new node back to heap
    heap << Node.new(new_value, new_depth)
  end
  
  ans = max_depth if valid && max_depth < ans
end

puts ans
0