結果
| 問題 | No.3297 Bake Cookies | 
| コンテスト | |
| ユーザー |  | 
| 提出日時 | 2025-10-05 14:05:33 | 
| 言語 | Ruby (3.4.1) | 
| 結果 | 
                                AC
                                 
                             | 
| 実行時間 | 626 ms / 2,000 ms | 
| コード長 | 4,013 bytes | 
| コンパイル時間 | 199 ms | 
| コンパイル使用メモリ | 8,064 KB | 
| 実行使用メモリ | 37,556 KB | 
| 最終ジャッジ日時 | 2025-10-05 14:06:15 | 
| 合計ジャッジ時間 | 15,337 ms | 
| ジャッジサーバーID (参考情報) | judge5 / judge2 | 
(要ログイン)
| ファイルパターン | 結果 | 
|---|---|
| other | AC * 27 | 
コンパイルメッセージ
Main.rb:16: warning: 'frozen_string_literal' is ignored after any tokens Syntax OK
ソースコード
# Kept libraries:
#   (none)
# Expanded libraries:
# - ac-library-rb/priority_queue
# Errored libraries:
#   (none)
# Removed libraries:
#   (none)
#
# ------------------------------------------------------------------------------
# frozen_string_literal: true
# This file is expanded by nanacl.
main = -> do # =================================================================
# frozen_string_literal: true
# require "ac-library-rb/priority_queue" # (expanded: L38)
in_n, in_m, in_t = gets.chomp.split.map(&:to_i)
in_a = gets.chomp.split.map(&:to_i)
pq = AcLibraryRb::PriorityQueue.new { |a, b| a < b }
num_imos = Array.new(in_m + 1, 0)
num_imos[0] = in_n
tally = in_a.tally
1.upto(in_n) do |k|
  v = tally[k] || 0
  num_imos[v] -= 1
  pq << v
end
num = [0]
num_imos.each { |d| num << num[-1] + d }
in_m.downto(1) do |i|
  next if num[i] == 0
  willbe = [pq.top + in_t * num[i], i - 1].max
  if willbe < i
    pq << pq.pop + in_t * num[i]
  else
    puts i
    exit
  end
end
end # --------------------------------------------------------------------------
# === dependencies -------------------------------------------------------------
# == ac-library-rb/priority_queue from main ------------------------------------
module AcLibraryRb
  # Priority Queue
  # Reference: https://github.com/python/cpython/blob/main/Lib/heapq.py
  class PriorityQueue
    # By default, the priority queue returns the maximum element first.
    # If a block is given, the priority between the elements is determined with it.
    # For example, the following block is given, the priority queue returns the minimum element first.
    # `PriorityQueue.new { |x, y| x < y }`
    #
    # A heap is an array for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for all k, counting elements from 0.
    def initialize(array = [], &comp)
      @heap = array
      @comp = comp || proc { |x, y| x > y }
      heapify
    end
    def self.max(array)
      new(array)
    end
    def self.min(array)
      new(array){ |x, y| x < y }
    end
    def self.[](*array, &comp)
      new(array, &comp)
    end
    attr_reader :heap
    alias to_a heap
    # Push new element to the heap.
    def push(item)
      shift_down(0, @heap.push(item).size - 1)
      self
    end
    alias << push
    alias append push
    # Pop the element with the highest priority.
    def pop
      latest = @heap.pop
      return latest if empty?
      ret_item = heap[0]
      heap[0] = latest
      shift_up(0)
      ret_item
    end
    # Get the element with the highest priority.
    def get
      @heap[0]
    end
    alias top get
    alias first get
    # Returns true if the heap is empty.
    def empty?
      @heap.empty?
    end
    def size
      @heap.size
    end
    def to_s
      "<#{self.class}: @heap:(#{heap.join(', ')}), @comp:<#{@comp.class} #{@comp.source_location.join(':')}>>"
    end
    private
    def heapify
      (@heap.size / 2 - 1).downto(0) { |i| shift_up(i) }
    end
    def shift_up(pos)
      end_pos = @heap.size
      start_pos = pos
      new_item = @heap[pos]
      left_child_pos = 2 * pos + 1
      while left_child_pos < end_pos
        right_child_pos = left_child_pos + 1
        if right_child_pos < end_pos && @comp.call(@heap[right_child_pos], @heap[left_child_pos])
          left_child_pos = right_child_pos
        end
        # Move the higher priority child up.
        @heap[pos] = @heap[left_child_pos]
        pos = left_child_pos
        left_child_pos = 2 * pos + 1
      end
      @heap[pos] = new_item
      shift_down(start_pos, pos)
    end
    def shift_down(star_pos, pos)
      new_item = @heap[pos]
      while pos > star_pos
        parent_pos = (pos - 1) >> 1
        parent = @heap[parent_pos]
        break if @comp.call(parent, new_item)
        @heap[pos] = parent
        pos = parent_pos
      end
      @heap[pos] = new_item
    end
  end
  HeapQueue = PriorityQueue
end
# ==============================================================================
main.call
            
            
            
        