COCI '17 Contest 4 #5 Krov

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.5s
Memory limit: 128M

Problem type

You are given a histogram consisting of N columns of heights X_1, X_2, \dots X_N, respectively. The histogram needs to be transformed into a roof using a series of operations. A roof is a histogram that has the following properties:

  • A single column is called the top of the roof. Let it be the column at position i.
  • The height of the column at position j\ (1 \le j \le N) is h_j = h_i - |i - j|.
  • All heights h_j are positive integers.

An operation can be increasing or decreasing the heights of a column of the histogram by 1. It is your task to determine the minimal number of operations needed in order to transform the given histogram into a roof.

Input Specification

The first line of input contains the number N\ (1 \le N \le 10^5), the number of columns in the histogram. The following line contains N numbers X_i\ (1 \le X_i \le 10^9), the initial column heights.

Output Specification

You must output the minimal number of operations from the task.


In test cases worth 60% of total points, it will hold N \le 5\,000.

Sample Input 1

1 1 2 3

Sample Output 1


Explanation for Sample Output 1

​By increasing the height of the second, third, and fourth column, we created a roof where the fourth column is the top of the roof.

Sample Input 2

4 5 7 2 2

Sample Output 2


Explanation for Sample Output 2

By decreasing the height of the third column three times, and increasing the height of the fourth column, we transformed the histogram into a roof. The example is illustrated below.

Sample Input 3

4 5 6 5 4 3

Sample Output 3



There are no comments at the moment.