Codeforces Round 787 (Div. 3) |
---|
Закончено |
Настя испекла $$$m$$$ блинов и разложила по $$$n$$$ тарелкам. Тарелки стоят в одном ряду и пронумерованы слева направо. На тарелку с номером $$$i$$$ она положила $$$a_i$$$ блинчиков.
Увидев тарелки, Влад решил привнести порядок в стопки и переложить некоторые блинчики. За один ход он может переложить один блинчик с любой тарелки на соседнюю, то есть выбрать тарелку $$$i$$$ ($$$a_i > 0$$$) и сделать одно из следующих действий:
Влад хочет сделать массив $$$a$$$ невозрастающим, переложив при этом как можно меньше блинчиков. Помогите ему найти минимальное количество перекладываний, необходимых для этого.
Массив $$$a=[a_1, a_2,\dots,a_n]$$$ называется невозрастающим, если $$$a_i \ge a_{i+1}$$$ для всех $$$i$$$ от $$$1$$$ до $$$n-1$$$.
Первая строка входных данных содержит два числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 250$$$) — количество тарелок и количество блинчиков соответственно.
Вторая строка содержит $$$n$$$ чисел $$$a_i$$$ ($$$0 \le a_i \le m$$$), сумма всех $$$a_i$$$ равна $$$m$$$.
Выведите единственное число — минимальное количество перекладываний, необходимое чтобы сделать массив $$$a$$$ невозрастающим.
6 19 5 3 2 3 3 3
2
3 6 3 2 1
0
3 6 2 1 3
1
6 19 3 4 3 3 5 1
3
10 1 0 0 0 0 0 0 0 0 0 1
9
В первом примере нужно сначала переложить блинчик с тарелки $$$1$$$, после чего $$$a = [4, 4, 2, 3, 3, 3]$$$. После необходимо переложить блинчик с тарелки $$$2$$$ на тарелку $$$3$$$ и массив станет невозрастающим $$$a = [4, 3, 3, 3, 3, 3]$$$.
Название |
---|