Overview

In this problem, there are \(N\) potted plants where \(D\) milliliters of water evaporate daily. Aoki can perform a “mischief that sets the water level to 0” up to \(K\) times (at most once per day) optimally. We need to find the minimum number of plants that will have at least \(1\) milliliter of water remaining after \(M\) days.

---

Analysis

At first glance, it might seem like a complex simulation is required. However, since the plants do not affect each other, if we focus on “how each plant transitions individually,” a very simple pattern emerges.

1. Plants that survive if Aoki does nothing

Let’s consider the condition for plant \(i\) to have at least \(1\) milliliter of water remaining after \(M\) days if Aoki does not play any mischief at all. Since \(D\) milliliters of water evaporate each day, a total of \(M \times D\) milliliters will evaporate over \(M\) days. Therefore, for the water level to remain at \(1\) or more after \(M\) days, the initial water level \(A_i\) must satisfy the following condition:

\[A_i - M \times D \ge 1 \iff A_i \ge M \times D + 1\]

Plants that do not satisfy this condition (\(A_i < M \times D + 1\)) will naturally have their water level drop to \(0\) even if Aoki does nothing. Since Aoki wants to minimize the number of surviving plants, there is no need to play mischief on these plants.

Thus, the only targets Aoki should aim for are “plants that would have \(1\) or more milliliters remaining after \(M\) days if left alone” (plants with \(A_i \ge M \times D + 1\)). Let \(S\) be the total number of such plants.

2. Maximum number of mischiefs Aoki can perform

Aoki wants to wither (reduce the water level to \(0\) for) as many of the \(S\) target plants as possible. The maximum number of plants Aoki can wither in \(M\) days is determined by the following constraints:

1. Maximum number of mischiefs: He can perform at most \(K\) mischiefs in total.
2. Time constraint: Since he can only act once per day, he can perform at most \(M\) mischiefs over \(M\) days.
3. Number of targets: There are only \(S\) target plants to begin with (there is no point in choosing the same plant multiple times).

Since all three constraints must be satisfied, the maximum number of plants Aoki can wither is the minimum of these values, which is \(\min(S, M, K)\) plants.

3. Number of plants remaining in the end

Since Aoki acts optimally, he will target and wither exactly \(\min(S, M, K)\) plants out of the \(S\) target plants. Therefore, the final number of surviving plants can be found as follows:

\[\text{Surviving plants} = S - \min(S, M, K)\]

---

Algorithm

1. Calculate the threshold water level \(\text{limit} = M \times D + 1\).
2. Check the initial water level \(A_i\) of each plant and count the number of plants \(S\) that satisfy \(A_i \ge \text{limit}\).
3. Calculate the number of plants Aoki can wither, \(\text{kill} = \min(S, M, K)\).
4. Output the final answer, \(S - \text{kill}\).

---

Complexity

• Time Complexity: \(O(N)\) We iterate through the initial water level \(A_i\) of each plant once to compare it with the threshold, so the process completes in linear time with respect to the number of plants \(N\). Since \(N \le 10^6\), this easily runs within the time limit.

• Space Complexity: \(O(N)\) If we store all inputs in an array to process them, the space complexity will be \(O(N)\).

---

Key Implementation Points

• Fast I/O: Since the number of inputs can be large in Python (up to \(10^6\)), instead of repeatedly calling input(), you can significantly reduce the execution time by reading all inputs at once using sys.stdin.read().split().

• Beware of Overflow: Since \(M \le 10^9\) and \(D \le 10^9\), \(\text{limit} = M \times D + 1\) can be up to \(10^{18} + 1\). When using statically typed languages like C++, you must use 64-bit integer types (such as long long) instead of 32-bit integer types (int). In Python, integers are automatically handled as arbitrary-precision integers, so you do not need to worry about the type.

  Source Code

import sys


def solve():
    # 入力をすべて取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    M = int(input_data[1])
    D = int(input_data[2])
    K = int(input_data[3])

    # いたずらがなくてもM日後に水量が1以上残るための最小初期水量
    limit = M * D + 1

    # 条件を満たす鉢植えの数をカウント
    S_count = 0
    for i in range(4, 4 + N):
        if int(input_data[i]) >= limit:
            S_count += 1

    # 青木君が0にできる鉢植えの最大数
    # 1日に1回しかいたずらできず、合計K回までなので、最大で min(M, K) 個
    kill = min(S_count, M, K)

    # 最終的に残る鉢植えの数
    ans = S_count - kill
    print(ans)


if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3.5-flash-high.