Overview

In this problem, we are asked to find the number of flowerpots that will have at least \(1\text{ mL}\) of water remaining in a flowerbed where water decreases due to evaporation and Aoki’s mischief.

At first glance, it seems to require a complex simulation. However, by clarifying “flowerpots that run out of water by evaporation alone” and “the maximum number of times Aoki can interfere”, we can find the answer with a very simple calculation.

Analysis

1. Flowerpots that survive if Aoki does nothing

Since \(D\text{ mL}\) of water evaporates every day for \(M\) days, the maximum amount of water lost over \(M\) days is \(M \times D\text{ mL}\). If Aoki does not do any mischief, the condition for flowerpot \(i\) to have at least \(1\text{ mL}\) of water remaining is as follows:

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

Let \(S\) be the number of flowerpots that satisfy this condition (i.e., water remains even if left alone). Conversely, flowerpots with \(A_i \le M \times D\) will have \(0\text{ mL}\) of water due to evaporation alone, even if Aoki does nothing.

2. Maximum number of “mischiefs” Aoki can perform

Aoki’s goal is to minimize the number of surviving flowerpots. Therefore, Aoki will prioritize targeting the \(S\) flowerpots that would otherwise survive, and discard their water.

The number of times Aoki can perform mischief is determined by the following two constraints: - The maximum number of mischiefs is \(K\). - Mischief can only be performed once a day, and since the period is \(M\) days, he can perform it at most \(M\) times.

Therefore, the maximum number of flowerpots that Aoki can actually reduce to \(0\) is \(\min(K, M)\).

3. Result of optimal actions

Aoki can choose at most \(\min(K, M)\) flowerpots from the \(S\) flowerpots that are expected to survive and definitely wither them (reduce their water to \(0\)). Therefore, the final number of surviving flowerpots is \(S\) minus the number of flowerpots ruined by Aoki.

However, since the number of surviving flowerpots cannot be less than \(0\), the required answer is:

\[\max(0, S - \min(K, M))\]

Algorithm

1. For each flowerpot \(i\), determine if \(A_i > M \times D\) holds, and count the number of satisfying flowerpots as \(S\).
2. Calculate the maximum number of times Aoki can act, aoki_ops \(= \min(K, M)\).
3. Output the final answer \(\max(0, S - \text{aoki\_ops})\).

Complexity

• Time Complexity: \(O(N)\) Since the check \(A_i > M \times D\) is performed once for each flowerpot, the processing completes in time proportional to \(N\).
• Space Complexity: \(O(N)\) The size of the array to store the input values of \(A_i\) is \(N\).

Implementation Points

• Preventing Overflow From the constraints, \(M \le 10^9\) and \(D \le 10^9\), so the value of \(M \times D\) can reach up to \(10^{18}\). In C++’s standard 64-bit integer type (long long), there is a risk of overflow during the multiplication process. Therefore, in the accepted code, a 128-bit integer type __int128_t is used to perform the comparison safely.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // Optimize standard I/O operations for competitive programming
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long N, M, D, K;
    if (!(cin >> N >> M >> D >> K)) return 0;

    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    // Use __int128_t to prevent overflow when multiplying M and D
    __int128_t loss = (__int128_t)M * D;

    long long S = 0;
    for (int i = 0; i < N; ++i) {
        if ((__int128_t)A[i] > loss) {
            S++;
        }
    }

    long long aoki_ops = min(K, M);
    long long ans = max(0LL, S - aoki_ops);

    cout << ans << "\n";

    return 0;
}

---

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