Overview

For each flowerpot, we determine whether water remains after \(M\) days if there is no mischief, and then subtract the maximum number of flowerpots Aoki can ruin from that count.

Analysis

First, let us consider the case where there is no mischief at all.

Each day, the water level in each flowerpot decreases by \(D\), so after \(M\) days, it decreases by a total of \(M \times D\).
Therefore, the condition for flowerpot \(i\) to survive with a water level of at least \(1\) after \(M\) days is:

\[ A_i - M \times D \geq 1 \]

Since these are integers, this can be rewritten as:

\[ A_i > M \times D \]

In other words, flowerpots with \(A_i \leq M \times D\) from the beginning will run out of water after \(M\) days even if Aoki does nothing.

On the other hand, flowerpots with \(A_i > M \times D\) will survive unless Aoki tampers with them.
Since Aoki can act at most once at the beginning of each day, the maximum number of pranks he can actually play in \(M\) days is \(M\).
Also, since the upper limit on the total number of pranks is \(K\), the maximum number of times he can actually play a prank is:

\[ \min(K, M) \]

times.

If Aoki acts optimally, he will prioritize ruining the flowerpots that are scheduled to survive by reducing their water level to \(0\).
Although he can choose the same flowerpot multiple times, there is no point in choosing the same one repeatedly, so he will target as many different surviving flowerpots as possible.

Thus, if we let survive be the number of flowerpots that would survive without any mischief, the answer is:

\[ \max(0, \text{survive} - \min(K, M)) \]

For example, when \(M=2\) and \(D=2\), the total decrease is \(4\).
If the initial water levels are \([10, 5, 3]\), only the \(2\) pots with levels \(10\) and \(5\) (which are greater than \(4\)) will survive naturally.
If \(K=1\), Aoki can ruin one of them, so the answer is \(1\).

Naively simulating the process for \(M\) days will result in a Time Limit Exceeded (TLE) because \(M\) can be up to \(10^9\).
It is sufficient to perform the check for each flowerpot only once.

Algorithm

1. Calculate \(M \times D\) and let this be threshold.
2. For the initial water level \(A_i\) of each flowerpot, if \(A_i > \text{threshold}\), it will survive without mischief, so increment survive by 1.
3. The number of times Aoki can actually play a prank is min(K, M).
4. Output max(0, survive - min(K, M)) as the answer.

Complexity

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

Implementation Details

Since \(M\) and \(D\) can be up to \(10^9\), their product \(M \times D\) can be up to \(10^{18}\).
This does not fit in a standard 32-bit integer (int), so you need to use a 64-bit integer type (such as long long in C++).

Also, note that the condition for the water level to remain at least \(1\) is \(A_i > M \times D\), not \(A_i \geq M \times D\).
If \(A_i = M \times D\), the water level after \(M\) days will be exactly \(0\), so it will not survive.

Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long N, M, D, K;
    cin >> N >> M >> D >> K;

    long long threshold = M * D;
    long long survive = 0;

    for (int i = 0; i < N; i++) {
        long long A;
        cin >> A;
        if (A > threshold) survive++;
    }

    long long attacks = min(K, M);
    cout << max(0LL, survive - attacks) << '\n';

    return 0;
}

---

This editorial was generated by gpt-5.5-high.