Water deposits P41867
There are n water deposits in a line. They are so huge that they can be considered to have infinite capacity. Initially, each deposit i has ℓi liters in it. You have a pump that you can use to transfer water from any deposit i to any adjacent deposit (i − 1 or i + 1). Each use of the pump to transfer water between two deposits has cost p + ℓ, where p is a constant cost to connect two adjacent deposits, and ℓ is the number of liters transferred. Your goal is to minimize the cost to equally distribute the water among all the deposits.
Input
Input consists of several cases, each with n and p, followed by ℓ1, …, ℓn. You can assume 1 ≤ n ≤ 105, 0 ≤ p ≤ 109, 0 ≤ ℓi ≤ 109, and that the sum of all ℓi’s is a multiple of n.
Output
For each case, print the minimum cost to equally distribute the water among all the deposits.
Input
4 42 5 5 5 5 1 8 100 7 100 10 30 14 6 50 15 15 8 10 0 0 0 0 0 0 1000000000 1000000000
Output
0 0 551 6000000070
- Author
- Jordi Cortadella
- Language
- English
- Official solutions
- C++
- User solutions
- C++