Overview

This is a problem where you compare the total amount of water needed for the flower pots with the amount of water in the watering can, and calculate the cost of purchasing the shortfall from the water supply.

Analysis

This problem is very simple and can be broken down into the following two cases: 1. If the water in the watering can \(S\) is greater than or equal to the total amount of water needed for all flower pots: there is no need to purchase water from the water supply (0 yen) 2. If the water in the watering can \(S\) is insufficient: you need to purchase the shortfall \((total - S)\) at a unit price of \(C\) yen

Although the input size is large (\(N \leq 10^6\)), the required computation is only a simple summation and comparison, so it can be processed efficiently.

Algorithm

1. Calculate the total amount of water needed for all flower pots: \(total\_water\_needed = R_1 + R_2 + \cdots + R_N\)
2. Compare the water in the watering can \(S\) with the total
3. If \(S \geq total\_water\_needed\), output 0
4. Otherwise, output the amount obtained by multiplying the shortfall \((total\_water\_needed - S)\) by the unit price \(C\)

Complexity

• Time complexity: \(O(N)\) (to compute the sum of the required water amounts for \(N\) flower pots)
• Space complexity: \(O(N)\) (for the array storing the required water amounts for the flower pots)

Implementation Notes

• Since the input values can be large (\(S \leq 10^{12}\)), make sure they are handled correctly with the appropriate integer type

• Clearly handle the conditional branching for whether the total required water amount for all flower pots is at most \(S\)

• Since this can be solved with simple arithmetic calculations only, no complex data structures or algorithms are needed

  Source Code

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    S = int(data[1])
    C = int(data[2])
    R_list = list(map(int, data[3:3+n]))
    
    total_water_needed = sum(R_list)
    if S >= total_water_needed:
        print(0)
    else:
        shortage = total_water_needed - S
        cost = shortage * C
        print(cost)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.