Overview

This problem asks for the number of surviving potted plants (water amount \(\geq 1\) ml) after \(M\) days of evaporation. Aoki acts optimally to minimize the number of surviving plants.

Analysis

Considering only evaporation

First, let’s consider the case without Aoki’s mischief. The water amount in pot \(i\) after \(M\) days is \(\max(0, A_i - M \cdot D)\).

Thus, the condition for the water amount to remain at least \(1\) after \(M\) days is:

\[A_i - M \cdot D \geq 1 \iff A_i \geq M \cdot D + 1\]

Let this threshold be \(T = M \cdot D + 1\), and let \(S\) be the number of pots satisfying \(A_i \geq T\).

Effect of Aoki’s mischief

If Aoki sets the water in a pot to \(0\), it remains \(0\) even if it evaporates afterwards. In other words, he can definitely wither any pot with a single action.

There is no need to perform an action on the same pot multiple times (since the water amount becomes \(0\) in one action and does not recover).

Aoki’s optimal strategy

Aoki should target the pots that would “survive if left alone” (those with \(A_i \geq T\)). This is because targeting a pot already destined to wither is pointless.

Aoki can only act at most once per day, and can act across all \(M\) days. Furthermore, since there is a limit of at most \(K\) total actions, the number of times he can actually act is \(\min(K, M)\) times.

Conclusion

The number of surviving pots is:

\[\text{answer} = \max(0,\ S - \min(K, M))\]

Algorithm

1. Calculate the threshold \(T = M \times D + 1\)
2. Count the number of pots \(S\) that satisfy \(A_i \geq T\)
3. Calculate Aoki’s effective number of actions \(\min(K, M)\)
4. Output \(\max(0, S - \min(K, M))\)

Example

For \(N=5,\ M=3,\ D=2,\ K=1,\ A = [10, 5, 8, 3, 7]\):

• Threshold \(T = 3 \times 2 + 1 = 7\)
• The pots satisfying \(A_i \geq 7\) are \(A_1=10, A_3=8, A_5=7\), which is \(3\) pots \(\to S=3\)
• Effective actions \(= \min(1, 3) = 1\)
• Answer \(= \max(0, 3 - 1) = 2\)

Complexity

• Time Complexity: \(O(N)\) (just scanning each pot once)
• Space Complexity: \(O(1)\) (sequential processing without storing the array)

Key Implementation Points

• Overflow prevention: Since \(M \times D\) can be up to \(10^9 \times 10^9 = 10^{18}\), you must use long long. The threshold \(T = M \cdot D + 1\) also fits within the range of long long (up to approximately \(10^{18} + 1\)).

• Minimum of \(K\) and \(M\): Since Aoki can only act at most once per day, even if \(K > M\), he can actually act at most \(M\) times. Forgetting this constraint will lead to WA.

• Fast I/O: Since \(N\) can be up to \(10^6\), we use ios_base::sync_with_stdio(false) and cin.tie(NULL) to speed up the input.

  Source Code

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    long long N, M, D, K;
    cin >> N >> M >> D >> K;
    
    long long threshold = M * D + 1;
    
    long long S = 0;
    for (long long i = 0; i < N; i++) {
        long long A;
        cin >> A;
        if (A >= threshold) {
            S++;
        }
    }
    
    long long effective_K = min(K, M);
    long long answer = max(0LL, S - effective_K);
    
    cout << answer << endl;
    
    return 0;
}

---

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