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

Copy

6
4 3 2 5 3 5

Sample Output

Copy

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]$ $[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 \leq n \leq 10$ .
For $70\%$ $70 %$ of test data, $1 \le n \le 1000$ $1 \leq n \leq 1000$ .
For $100\%$ $100 %$ of test data, $1 \le n \le 100\,000$ $1 \leq n \leq 100 000$ , $0 \le d_i \le 10\,000$ $0 \leq d_{i} \leq 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.