Overview

This is a problem where, in a balloon-popping game, we need to find the maximum number of balloons that can be popped with a limited number of dart throws.

Analysis

In this problem, the goal is to pop as many balloons as possible within \(K\) throws. A naive approach would be to calculate the minimum number of throws needed for each balloon individually, then greedily select them in ascending order of cost.

However, the number of balloons and darts can be up to \(2 \times 10^5\), and \(K\) can be extremely large (up to \(10^{18}\)), making it impossible to try all combinations. The key insight is to shift perspective from “which balloons to pop” to “how to efficiently pop as many balloons as possible.”

Here is the crucial observation:

The minimum number of throws needed to pop each balloon is minimized by using the dart with the highest attack power (maximum attack power).

This is because you can target the same balloon multiple times and use any dart each time, so using the most efficient dart (i.e., the one with maximum attack power) allows you to pop a balloon in the fewest throws.

Therefore, for each balloon \(i\), the minimum number of throws needed to pop it is the ceiling of its durability \(H_i\) divided by the maximum attack power \(max\_P\): $\( \text{min\_darts}_i = \left\lceil \frac{H_i}{max\_P} \right\rceil \)$

By computing this value for all balloons and sorting them in ascending order, we can “greedily select in order of lowest cost.” In other words, by popping balloons in order from those requiring the fewest throws, as long as the cumulative total does not exceed \(K\), we obtain the maximum count.

Algorithm

1. Let \(max\_P\) be the attack power of the dart with the highest attack power.
2. For each balloon \(i\), compute \(\left\lceil \frac{H_i}{max\_P} \right\rceil\) and store it in the list min_darts_needed.
3. Sort min_darts_needed in ascending order.
4. Starting from the beginning of the sorted list, select balloons as long as the cumulative total does not exceed \(K\), and count how many are selected.
5. The count is the answer.

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(N)\)

Implementation Notes

• Ceiling division \(\left\lceil a / b \right\rceil\) can be computed as (a + b - 1) // b (for integers).

• It suffices to find the dart with the maximum attack power once; there is no need to search for it each time.

• Precompute the minimum number of throws needed for each balloon before sorting.

  Source Code

import sys
import heapq
from bisect import bisect_left

def input():
    return sys.stdin.readline().rstrip()

def main():
    N, M, K = map(int, input().split())
    H = list(map(int, input().split()))
    P = list(map(int, input().split()))
    
    # 最大攻撃力で割れる風船の上限を求める
    max_P = max(P)
    
    # 各風船を割るのに必要な最小投擲回数を求める
    # 各H[i]について、ceil(H[i] / max_P) を計算
    min_darts_needed = []
    for h in H:
        if h <= max_P:
            min_darts_needed.append(1)
        else:
            # ceil(h / max_P)
            min_darts_needed.append((h + max_P - 1) // max_P)
    
    # 投擲回数の最小値でソートして、貪欲に割れる風船を選ぶ
    min_darts_needed.sort()
    
    count = 0
    total = 0
    for d in min_darts_needed:
        if total + d <= K:
            total += d
            count += 1
        else:
            break
    
    print(count)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.