Overview

We will determine for each flowerpot whether water remains after \(M\) days without any interference, and then consider how many of those will be reduced by Aoki’s mischief.

Analysis

First, let’s consider the case without any mischief.

The amount of water in flowerpot \(i\) decreases by a total of \(M \times D\) milliliters over \(M\) days.
Therefore, the condition for at least \(1\) milliliter of water to remain after \(M\) days is

\[ A_i > M \times D \]

If \(A_i = M \times D\), the water level becomes exactly \(0\), so it does not survive.

Next, let’s consider Aoki’s mischief.

At the beginning of each day, Aoki can set the water of at most one flowerpot to \(0\).
Once a flowerpot is set to \(0\), no water is replenished afterwards, so water will never remain in it at the end.

In other words, with one mischief, Aoki can reduce the number of “originally surviving flowerpots” by at most \(1\).

However, since Aoki can act at most once per day over \(M\) days, the number of times he can actually use his mischief is

\[ \min(K, M) \]

times.

For example, if there are \(5\) flowerpots that would originally survive and Aoki can perform mischief \(3\) times, the final number of surviving flowerpots is

\[ 5 - 3 = 2 \]

On the other hand, if only \(2\) flowerpots would originally survive but Aoki can perform mischief \(5\) times, the remaining count does not become negative and is \(0\).

A naive simulation of the evaporation over \(M\) days will not run in time, as \(M\) can be up to \(10^9\).
Furthermore, we do not need to think about which flowerpot to attack on which day in detail. In the end, only “how many originally surviving flowerpots can be eliminated” matters.

Algorithm

1. Calculate \(threshold = M \times D\).
2. For each flowerpot, if \(A_i > threshold\), it would originally survive, so we count it.
3. Let the number of effective mischiefs Aoki can perform be $\( attacks = \min(K, M) \)$
4. The answer is $\( \max(0, survive - attacks) \)$

Here, \(survive\) is the number of flowerpots that would survive without any mischief.

Complexity

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(N)\)

Since the input is read all at once, the space complexity in implementation is \(O(N)\).
If we implement it by reading the input sequentially, the auxiliary space complexity can be \(O(1)\).

Implementation Notes

Since \(M\) and \(D\) can be up to \(10^9\), \(M \times D\) can be up to \(10^{18}\).
In Python, we do not need to worry about integer overflow, but in other languages, we must use a 64-bit integer type.

Also, note that the condition for survival is not \(A_i \geq M \times D\), but rather

\[ A_i > M \times D \]

This is because if \(A_i\) is exactly \(M \times D\), the final water level becomes \(0\).

Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    N = int(data[0])
    M = int(data[1])
    D = int(data[2])
    K = int(data[3])

    threshold = M * D
    survive = 0

    for x in data[4:]:
        if int(x) > threshold:
            survive += 1

    attacks = K if K < M else M
    ans = survive - attacks
    if ans < 0:
        ans = 0

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.