Задача . Landscaping

‘ ¤ б®бв®Ёв Ё§ Ї®б«Ґ¤®ў вҐ«м­®бвЁ Ё§ \(N\) Є«г¬Ў (\(1 \leq N \leq 100,000\)), ѓ¤Ґ Є«г¬Ў  \(i\) Ё§­ з «м­® ᮤҐа¦Ёв \(A_i\) Ґ¤Ё­Ёж ¤са­ . ”„ е®зҐв ८࣠­Ё§®ў вм б ¤ в Є, зв®Ўл Є ¦¤ п Є«г¬Ў  бв «  ᮤҐа¦ вм \(B_i\) Ґ¤Ё­Ёж ¤са­ . \(A_i\) Ё \(B_i\) - жҐ«лҐ зЁб«  ў Ё­вҐаў «Ґ \(0 \ldots 10\).

„«п Ё§¬Ґ­Ґ­Ёп « ­¤и дв  ”„ Ё¬ҐҐв ­ҐбЄ®«мЄ® ў аЁ ­в®ў: ®­ ¬®¦Ґв ЄгЇЁвм ®¤­г Ґ¤Ё­Ёжг ¤са­  Ё Ї®«®¦Ёвм Ґс ­  «оЎго Є«г¬Ўг §  \(X\) Ґ¤Ё­Ёж ¤Ґ­ҐЈ. Ћ­ ¬®¦Ґв б­пвм ®¤­г Ґ¤Ё­Ёжг ¤са­  б «оЎ®© Є«г¬Ўл Ё Їа®¤ вм Ґс §  \(Y\) Ґ¤Ё­Ёж ¤Ґ­ҐЈ. Ћ­ в Є¦Ґ ¬®¦Ґв ЏҐаҐ¬ҐбвЁвм ®¤­г Ґ¤Ё­Ёжг ¤са­  б Є«г¬Ўл \(i\) ­  Є«г¬Ўг \(j\) §  \(Z\) times \(|i-j|\). ‚лзЁб«ЁвҐ ¬Ё­Ё¬ «м­го бв®Ё¬®бвм, §  Є®в®аго ”„ ¬®¦Ґв ўлЇ®«­Ёвм бў®© Їа®ҐЄв.

Џђ€Њ…ђ ‚‚Ћ„Ђ:

4 100 200 1
1 4
2 3
3 2
4 0

Џђ€Њ…ђ ‚›‚Ћ„Ђ:

210

‡ ¬ҐвЁ¬ зв® в Є п § ¤ з  ¤ ў « бм ў ®¤­®¬ Ё§ ЇаҐ¦­Ёе USACO-Є®­вҐбв®ў ­  га®ў­Ґ Silver. Ћ¤­ Є® ᥩз б бгйҐб⢥­­® 㬥­м襭® ўаҐ¬п ­  вҐбв.

Ђўв®а: Brian Dean Farmer John is building a nicely-landscaped garden, and needs to move a large amount of dirt in the process.

The garden consists of a sequence of \(N\) flowerbeds (\(1 \leq N \leq 100,000\)), where flowerbed \(i\) initially contains \(A_i\) units of dirt. Farmer John would like to re-landscape the garden so that each flowerbed \(i\) instead contains \(B_i\) units of dirt. The \(A_i\)'s and \(B_i\)'s are all integers in the range \(0 \ldots 10\).

To landscape the garden, Farmer John has several options: he can purchase one unit of dirt and place it in a flowerbed of his choice for \(X\) units of money. He can remove one unit of dirt from a flowerbed of his choice and have it shipped away for \(Y\) units of money. He can also transport one unit of dirt from flowerbed \(i\) to flowerbed \(j\) at a cost of \(Z\) times \(|i-j|\). Please compute the minimum total cost for Farmer John to complete his landscaping project.

210