Overview

This is a problem where you calculate the total amount of water needed for all flower pots, then compute the cost of purchasing the shortfall from the available water supply.

Analysis

First, calculate the total amount of water needed for all flower pots: \(total\_R = R_1 + R_2 + \cdots + R_N\). Since the amount of water on hand is \(S\) liters, the water shortage \(shortage\) can be calculated as \(total\_R - S\).

This can be divided into the following two cases: 1. When \(shortage > 0\) The water on hand alone is not enough, so you need to purchase \(shortage\) liters of water from the tap. Since the cost is \(C\) yen per liter, the total cost is \(shortage \times C\) yen. 2. When \(shortage \leq 0\) The water on hand is sufficient (or there is surplus), so there is no need to purchase water. Therefore, the cost is \(0\) yen.

Looking at the constraints, \(N \leq 10^6\) is very large, so a naive approach of processing inputs one by one (e.g., calling input() repeatedly in Python) may result in Time Limit Exceeded (TLE). Fast I/O or the use of built-in functions to efficiently compute the sum of an array is required.

Additionally, the total water needed \(total\_R\) can be up to \(10^6 \times 10^4 = 10^{10}\), which exceeds the range of a typical 32-bit integer (maximum approximately \(2 \times 10^9\)). Therefore, care must be taken to avoid overflow depending on the variable type.

Algorithm

1. Read the number of flower pots \(N\), the amount of water on hand \(S\), the unit price \(C\), and the amount of water needed for each flower pot \(R_1, \dots, R_N\) from the input.
2. Calculate the total water needed \(total\_R\).
3. Calculate the shortage \(shortage = total\_R - S\).
4. If \(shortage > 0\), output \(shortage \times C\); otherwise (if \(0\) or less), output \(0\).

Complexity

• Time complexity: \(O(N)\)
  • Computing the sum of \(N\) values \(R_i\) takes \(O(N)\) time. All other arithmetic operations and conditional checks complete in \(O(1)\).
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the input data as an array (list).

Implementation Notes

• Fast I/O: In Python, using sys.stdin.read().split() allows you to read and split the entire input at once, enabling very fast processing.

• Sum calculation: By combining sum() and map() as in sum(map(int, data[3:])), internally optimized and fast computation is possible.

• Overflow: In Python, there is no upper limit on integer size, so this is not a concern. However, when implementing in languages such as C++ or Java, you need to use 64-bit integer types (long long, long, etc.) for the variables holding the total \(total\_R\) and the final cost. Failing to do so will result in incorrect output (WA).

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    S = int(data[1])
    C = int(data[2])
    total_R = sum(map(int, data[3:]))
    
    shortage = total_R - S
    if shortage > 0:
        print(shortage * C)
    else:
        print(0)

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3.1-pro-thinking.