# 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