Overview

This is a problem where we determine whether all requests can be handled, given that the total processing capacity of \(N\) servers is at least the number of requests over \(M\) days.

Analysis

Key Insight

Each server has a processing capacity \(A_i\), and each day one request is assigned to exactly one server. Since Takahashi can choose the assignment “optimally,” he can freely distribute requests as long as each server’s capacity is not exceeded.

The important point here is that there are no constraints on the order or combination of request assignments. In other words, which day’s request is assigned to which server is entirely flexible, and the only thing we need to consider is “whether the total processing capacity of all servers can cover \(M\) requests.”

Concrete Examples

• For \(N = 3, M = 10, A = [3, 4, 5]\): the total is \(3 + 4 + 5 = 12 \geq 10\), so the answer is Yes
• For \(N = 2, M = 10, A = [3, 4]\): the total is \(3 + 4 = 7 < 10\), so the answer is No

If You Overthink It…

If you try to simulate “which day’s request is assigned to which server,” since \(M\) can be as large as \(10^9\), processing one day at a time would result in TLE. However, thanks to the insight above, simply comparing the total is sufficient.

Algorithm

1. Read \(N, M\).
2. Read the array \(A\).
3. Compute \(A_1 + A_2 + \cdots + A_N\).
4. If the total is at least \(M\), output Yes; otherwise, output No.

Why this is correct:

• When assigning \(c_i\) requests (\(0 \leq c_i \leq A_i\)) to each server \(i\), the condition for the existence of a tuple of non-negative integers satisfying \(c_1 + c_2 + \cdots + c_N = M\) is \(\sum A_i \geq M\).
• If \(\sum A_i \geq M\), we can distribute exactly \(M\) requests using, for example, a greedy approach that assigns requests to server \(1\) first up to its capacity, then to server \(2\), and so on.

Complexity

• Time complexity: \(O(N)\) (reading the array and computing the sum)
• Space complexity: \(O(N)\) (storing the array)

Implementation Notes

• Since \(A_i\) and \(M\) can each be up to \(10^9\) and \(N\) can be up to \(10^5\), the total can be on the order of \(10^{14}\). In C++ and similar languages, you need to use long long, but in Python there is no need to worry about integer overflow.

• Using Python’s sum() function, you can compute the total in a single line, making the code very concise.

  Source Code

N, M = map(int, input().split())
A = list(map(int, input().split()))
print("Yes" if sum(A) >= M else "No")

---

This editorial was generated by claude4.6opus-thinking.