Overview

Given that you can change the daily delivery capacity to \(K+x\) where \(0 \le x \le M\), find the minimum total number of days \(\sum_{i=1}^{N}\left\lceil \frac{A_i}{K+x}\right\rceil\).

Analysis

The key observation is the monotonicity: “increasing the number of items deliverable per day (the denominator) never increases the required number of days.”

• The required number of days for each destination \(i\) is \(f_i(d)=\left\lceil \frac{A_i}{d}\right\rceil\) (where \(d=K+x\)).
• As \(d\) increases, the amount deliverable per day increases, so \(\frac{A_i}{d}\) decreases. Therefore, even after taking the ceiling, the value stays the same or decreases — it never increases.
  • Example: When \(A_i=10\)
    \(d=3 \Rightarrow \lceil 10/3\rceil=4\)
    \(d=4 \Rightarrow \lceil 10/4\rceil=3\)
    \(d=5 \Rightarrow \lceil 10/5\rceil=2\)

Therefore, the total sum $\( F(d)=\sum_{i=1}^{N}\left\lceil \frac{A_i}{d}\right\rceil \)\( is also monotonically non-increasing with respect to \)d\(. This means the minimum is achieved when \)d\( is maximized within the allowed range (i.e., when \)x$ is maximized).

• Conclusion: The optimal choice is always \(x=M\) (maximize the capacity).

A brute-force search over \(x=0,1,2,\dots,M\) would be far too slow since \(M \le 10^9\), but thanks to the above monotonicity, no search is needed at all.

Algorithm

1. Compute the maximum delivery capacity \(C = K + M\).
2. Compute the answer as $\( \sum_{i=1}^{N}\left\lceil \frac{A_i}{C}\right\rceil \)$
3. The ceiling division can be computed using integer arithmetic: $\( \left\lceil \frac{a}{C}\right\rceil = \left\lfloor \frac{a + C - 1}{C}\right\rfloor \)$ In Python, this is (a + C - 1) // C.

Complexity

• Time complexity: \(O(N)\) (each \(A_i\) is processed exactly once)
• Space complexity: \(O(1)\) (no additional arrays needed if input is processed sequentially)

Implementation Notes

• Ceiling division using (a + C - 1) // C is both safe and fast.

• Since \(N\) can be up to \(2\times 10^5\), using sys.stdin.buffer.read() for fast input is effective in Python.

  Source Code

import sys

def main():
    it = map(int, sys.stdin.buffer.read().split())
    N = next(it)
    K = next(it)
    M = next(it)
    C = K + M
    ans = 0
    for _ in range(N):
        a = next(it)
        ans += (a + C - 1) // C
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.