Water deposits P41867


Statement
 

pdf   zip

thehtml

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.

Public test cases
  • 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
    
  • Information
    Author
    Jordi Cortadella
    Language
    English
    Official solutions
    C++
    User solutions
    C++