NOIP '18 P1 - Paving Roads

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

You have an array of length n that are initially zero. In each step, you may choose a consecutive interval [L,R] and increase the values by 1. Find the minimum number of operations required so that the i-th entry of the array is equal to d_i.

Input Specification

The input file has two lines. The first line has an integer n denoting the length of the array. The second line contains n integers separated by one space. The i-th integer denotes d_i.

Output Specification

The output contains only one integer denoting the minimum number of operations required.

Sample Input

4 3 2 5 3 5

Sample Output



One possible optimal solution is to choose [1,6], [1,6], [1,2], [1,1], [4,6], [4,4], [4,4], [6,6], [6,6] as the subintervals to increment.


For 30\% of test data, 1 \le n \le 10.
For 70\% of test data, 1 \le n \le 1000.
For 100\% of test data, 1 \le n \le 100\,000, 0 \le d_i \le 10\,000.


There are no comments at the moment.