Overview

This problem asks us to find the number of potted plants that can survive \(M\) days of evaporation, and subtract the number of plants that Aoki can wither by acting optimally.

Analysis

Natural Selection by Evaporation

First, let’s consider the case without Aoki’s mischief. After \(M\) days, the water level of potted plant \(i\) will be \(\max(0, A_i - M \times D)\). The condition for the water level to remain at least \(1\) milliliter is:

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

In other words, only the potted plants whose initial water level exceeds the threshold \(M \times D\) will survive naturally.

The Effect of Aoki’s Mischief

If Aoki sets the water level of a potted plant to \(0\), the water level remains \(0\) even with subsequent evaporation. Therefore, he can guarantee withering one potted plant per action.

Since Aoki acts optimally, he will only target the potted plants that would otherwise survive naturally (targeting plants that are already destined to wither is useless).

Constraints on the Number of Actions

Since Aoki can only act “once at the beginning of each day,” he can perform at most \(M\) actions over \(M\) days. Combined with the upper limit of \(K\) times, the number of times he can actually act is \(\min(K, M)\).

Concrete Example

For \(N=5, M=3, D=2, K=2, A = [10, 5, 7, 3, 20]\): - Threshold = \(3 \times 2 = 6\) - The 3 plants satisfying \(A_i > 6\) are \(A_1=10, A_3=7, A_5=20\) - Aoki’s effective number of actions = \(\min(2, 3) = 2\) - Answer = \(\max(0, 3 - 2) = 1\)

Algorithm

1. Calculate the threshold \(\text{threshold} = M \times D\).
2. Count the number of potted plants satisfying \(A_i > \text{threshold}\) (let this be count_surviving).
3. Let Aoki’s effective number of actions be \(\text{effective\_K} = \min(K, M)\).
4. The answer is \(\max(0, \text{count\_surviving} - \text{effective\_K})\).

Complexity

• Time Complexity: \(O(N)\) — simply scanning all potted plants once
• Space Complexity: \(O(N)\) — for reading the input (it can be \(O(1)\) if processed on the fly)

Implementation Points

• Beware of overflow in \(M \times D\). Since both \(M\) and \(D\) can be up to \(10^9\), their product can be up to \(10^{18}\). This is not an issue in Python as it supports arbitrary-precision integers, but in languages like C++, long long is required.

• In Python, reading the entire input at once using sys.stdin.buffer.read() allows for fast input processing even when \(N\) is up to \(10^6\).

• Do not overlook that the upper limit of Aoki’s actions is restricted not only by \(K\) but also by \(M\) (the number of days).

  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
    
    count_surviving = 0
    for i in range(4, 4 + N):
        if int(data[i]) > threshold:
            count_surviving += 1
    
    effective_K = min(K, M)
    
    answer = max(0, count_surviving - effective_K)
    print(answer)

main()

---

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