Overview

This is a problem where some tests are failing (final score is \(0\) or below), and we can use supplementary lessons (each one adds \(+P\) to any chosen test) up to \(K\) times to save as many failing tests as possible, minimizing the number of failing tests.

Analysis

There are two key observations:

1. Whether a test is failing is determined independently for each test

   • If we assign \(t\) supplementary lessons to a test with score \(H_i\), the final score becomes \(H_i + tP\).
   • To avoid failing, we need to find the minimum \(t\) such that \(H_i + tP \ge 1\) (since a score of \(0\) also counts as failing, we need “at least 1”).
   • In other words, once we know “how many supplementary lessons are needed to save each failing test,” the problem reduces to figuring out how many we can save within the limited budget of \(K\) lessons.

2. Greedily saving the ones that require the fewest lessons is optimal

   • The goal is to maximize the “number of tests saved (number of failing tests reduced).”
   • Saving one test always has the same value — “one fewer failing test” — so it’s optimal to save them in order of increasing cost (required number of lessons). This is the classic “maximum number of equal-value items within a budget” problem.

Naively simulating “where to assign each lesson one at a time” won’t work since \(K\) can be up to \(10^9\). Instead, we directly compute the number of lessons needed to save each test, sort them, and greedily select.

Deriving the Required Number of Lessons

For each failing test (\(H_i \le 0\)), we find the minimum \(t\): - Condition: \(H_i + tP \ge 1\) - Therefore: \(t \ge \dfrac{1 - H_i}{P}\)

Taking the minimum integer value: [ t = \left\lceil \frac{1 - H_i}{P} \right\rceil ] In code, this is computed using the following equivalent form (when \(H_i \le 0\)): [ t = \left\lfloor \frac{-H_i}{P} \right\rfloor + 1 ] (Example: \(H=-5, P=3\) gives \((-H)//P+1 = 5//3+1=2+1=3\) lessons, and \(-5+9=4\ge1\))

Algorithm

1. Scan all tests and count the number of failing tests red (those with \(H_i \le 0\)).
2. For each failing test, compute the “number of supplementary lessons needed to avoid failing”:
   \(c_i = (-H_i)//P + 1\), and store it in the array costs.
3. Sort costs in ascending order.
4. Greedily pick from the smallest cost, accumulating the total lessons used as long as it doesn’t exceed \(K\). Let fixed be the number of tests saved.
5. The answer is red - fixed (the remaining failing tests after saving).

Complexity

• Time complexity: \(O(N \log N)\) (letting \(M\) be the number of failing tests, sorting takes \(O(M \log M)\), and \(M = N\) in the worst case)
• Space complexity: \(O(N)\) (array to store the required number of lessons)

Implementation Notes

• A score of \(0\) also counts as failing, so the target is \(H_i + tP \ge 1\). Mistakenly using \(\ge 0\) will undercount by one lesson and result in WA.

• Although \(K\) can be as large as \(10^9\), we only loop over the length of costs (at most \(N\)), so it’s safe.

• Python integers don’t overflow, but in other languages, note that \(H_i\) and intermediate calculations can be on the order of \(10^9\), so be careful with data types.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K, P = map(int, input().split())
    H = list(map(int, input().split()))
    
    costs = []
    red = 0
    for h in H:
        if h <= 0:
            red += 1
            costs.append((-h) // P + 1)
    
    costs.sort()
    used = 0
    fixed = 0
    for c in costs:
        if used + c <= K:
            used += c
            fixed += 1
        else:
            break
    
    print(red - fixed)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.