NOIP '18 P1 - Paving Roads - DMOJ: Modern Online Judge

NOIP '18 P1 - Paving Roads

View as PDF

Submit solution

All submissions

Best submissions

Points: 7 (partial)

Time limit: 1.0s

Memory limit: 512M

Problem type

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

Input Specification

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

Output Specification

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

Sample Input

6
4 3 2 5 3 5

Sample Output

Explanation

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.

Constraints

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

Comments

1

maxcruickshanks commented on Aug. 18, 2022, 1:22 a.m.

Since the original data were weak, an additional test case was added, and all submissions were rejudged.

1

maxcruickshanks commented on Aug. 18, 2022, 1:16 p.m.

An additional test case was added again, and all submissions were rejudged.