Overview

This is a simple subtraction and multiplication problem where you need to find the cost of purchasing water from the tap to cover the shortage not supplied by the \(S\) liters of water in the watering can.

Analysis

• The total amount of water needed for all flower pots is \(R_1 + R_2 + \cdots + R_N\) liters.
• Since the watering can has \(S\) liters of water, the shortage is \(\text{total} - S\) liters.
• However, if the watering can has enough water (\(S \geq \text{total}\)), the shortage becomes a negative value, but in that case no water needs to be purchased from the tap, so the cost is \(0\) yen.
• Multiplying the shortage by the unit price \(C\) gives the answer.

Concrete example: If there are 3 flower pots requiring \(3, 5, 2\) liters of water (total of \(10\) liters), and the watering can has \(S = 6\) liters, the shortage is \(10 - 6 = 4\) liters. If \(C = 3\) yen/liter, the answer is \(4 \times 3 = 12\) yen.

This problem can be solved by simply computing the total and subtracting, so no special techniques are needed. However, since \(N\) can be as large as \(10^6\), the total must be computed in \(O(N)\) (which is easily done with a sum function).

Algorithm

1. Compute the total \(\text{total}\) of \(R_1, R_2, \ldots, R_N\).
2. Calculate the shortage as \(\text{shortage} = \max(0,\ \text{total} - S)\). Taking \(\max(0, \cdots)\) ensures the value does not become negative when there is enough water.
3. Output \(\text{shortage} \times C\) as the answer.

Complexity

• Time complexity: \(O(N)\) (for computing the sum of the array)
• Space complexity: \(O(N)\) (for storing the array \(R\))

Implementation Notes

• Since \(N\) can be up to \(10^6\) and \(R_i\) can be up to \(10^4\), the total can be as large as \(10^{10}\). Also, \(S\) can be up to \(10^{12}\). In Python, integer overflow does not occur, but when solving in C++ or similar languages, you need to use the long long type.

• It is important to use max(0, total - S) to prevent the shortage from becoming negative. This avoids outputting a negative cost when the watering can has excess water.

  Source Code

N, S, C = map(int, input().split())
R = list(map(int, input().split()))
total = sum(R)
shortage = max(0, total - S)
print(shortage * C)

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