Overview

We minimize the number of throws needed to pop each balloon, then pop balloons in order from fewest throws required, to find the maximum number of balloons that can be popped within \(K\) throws.

Analysis

Key Insight 1: You only need to use “the single dart with the highest attack power”

You can freely choose which dart to throw each time, and each dart can be used any number of times. Since a balloon pops when its durability drops to \(0\) or below, we want to minimize the number of throws needed to pop the same balloon.

Let \(p_{\max}=\max(P)\) be the maximum attack power among all darts. Then the minimum number of throws needed to pop a balloon with durability \(H\) is: - Using only the strongest dart: \(\left\lceil \dfrac{H}{p_{\max}} \right\rceil\) - Mixing in other darts can only result in a smaller damage per throw, so the number of throws can never be less than this

Therefore, the “minimum number of throws to pop each balloon” is always achieved by using only the strongest dart, and even in an optimal solution there is no need to use any other dart.

Key Insight 2: Once we know “the cost to pop each balloon,” we just pick them in ascending order

Let \(c_i\) be the number of throws (cost) needed to pop each balloon. The goal is to:

• Satisfy total cost \(\sum c_i \le K\)
• Maximize the number of balloons chosen

Since each balloon has the same value of “1 balloon popped,” it is optimal to pop them in order of increasing cost (this allows us to fit the maximum number of balloons).

Why a Naive Solution Fails

• \(K\) can be up to \(10^{18}\), so simulating one throw at a time is impossible.
• A DP approach that tracks the optimal dart choice for each balloon is also impractical with \(N, M\) up to \(2\times 10^5\).

The key is to reduce the problem to: “narrow down to only the strongest dart” → “compute the required number of throws per balloon” → “greedily pick in ascending order.”

Concrete Example

If \(P = [3, 5]\), then \(p_{\max}=5\). For balloon durabilities \(H=[4,9,10]\), the required throws are: - \(4\): \(\lceil 4/5\rceil=1\) - \(9\): \(\lceil 9/5\rceil=2\) - \(10\): \(\lceil 10/5\rceil=2\)

If \(K=3\), we add costs in ascending order: \(1+2=3\), so we can pop at most 2 balloons.

Algorithm

1. Find the maximum dart attack power \(p_{\max}=\max(P)\).
2. For each balloon \(i\), compute the minimum number of throws (cost) to pop it using only the strongest dart. [ c_i = \left\lceil \frac{Hi}{p{\max}} \right\rceil ] In integer arithmetic: [ c_i = \left\lfloor \frac{Hi + p{\max} - 1}{p_{\max}} \right\rfloor ]
3. Sort the cost array \(c\) in ascending order.
4. Add costs in ascending order, counting balloons as long as the cumulative sum does not exceed \(K\) (greedy).
5. Output the count.

Complexity

• Time complexity: \(O(N \log N + M)\) (\(O(M)\) for computing the maximum, \(O(N\log N)\) for sorting the costs)
• Space complexity: \(O(N)\) (to store the cost array)

Implementation Notes

• \(\left\lceil \dfrac{H}{p} \right\rceil\) is computed as (H + p - 1) // p (avoiding floating-point arithmetic).

• \(H_i, P_j, K\) can be up to \(10^{18}\), so 64-bit integers are required (Python’s int handles this safely).

• After sorting, you can stop early as soon as the cumulative sum exceeds \(K\), avoiding unnecessary computation.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    H = list(map(int, input().split()))
    P = list(map(int, input().split()))
    pmax = max(P)

    costs = [(h + pmax - 1) // pmax for h in H]
    costs.sort()

    s = 0
    ans = 0
    for c in costs:
        if s + c > K:
            break
        s += c
        ans += 1

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.