IMPACT Olympiad for teachers and coaches 2021 Problem G

Правка en1, от Temotoloraia, 2021-02-11 14:05:26

Can anyone solve this?

You are given array a1...n. We want to make a zero-array(array consisting only of zeroes) from it. You have 3 buttons:

1-button) Take an element ai, replace it with integer x such that |x−ai|≤1. The cost of using this button is 1 gold. 2-button) Take a range [l…r], increase all elements in this range by 1. The cost of using this button is X gold. 3-button) Take a range [l…r], decrease all elements in this range by 1. The cost of using this button is X gold. Find the minimum total gold to achieve zero-array. Input The first line contains two numbers n and X (1≤X≤n≤1000000).

The second line contains n numbers a1,a2,…,an(1≤ai≤1000000000) — array a.

Output Print a single integer — the minimum amount of gold to reach the zero-array.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Temotoloraia 2021-02-11 14:05:26 845 Initial revision (published)