codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

596B.md (1537B)


      1 Source: https://codeforces.com/problemset/problem/596/B
      2 
      3 B. Wilbur and Array
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Wilbur the pig is tinkering with arrays again. He has the array *a*1, *a*2, ..., *a**n* initially consisting of *n* zeros. At one step, he can choose any index *i* and either add 1 to all elements *a**i*, *a**i* + 1, ... , *a**n* or subtract 1 from all elements *a**i*, *a**i* + 1, ..., *a**n*. His goal is to end up with the array *b*1, *b*2, ..., *b**n*.
     22 
     23 Of course, Wilbur wants to achieve this goal in the minimum number of steps and asks you to compute this value.
     24 
     25 Input
     26 
     27 The first line of the input contains a single integer *n* (1 ≤ *n* ≤ 200 000) — the length of the array *a**i*. Initially *a**i* = 0 for every position *i*, so this array is not given in the input.
     28 
     29 The second line of the input contains *n* integers *b*1, *b*2, ..., *b**n* ( - 109 ≤ *b**i* ≤ 109).
     30 
     31 Output
     32 
     33 Print the minimum number of steps that Wilbur needs to make in order to achieve *a**i* = *b**i* for all *i*.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 5  
     41 1 2 3 4 5
     42 ```
     43 
     44 Output
     45 
     46 ```
     47 5
     48 ```
     49 
     50 Input
     51 
     52 ```
     53 4  
     54 1 2 2 1
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 3
     61 ```
     62 
     63 Note
     64 
     65 In the first sample, Wilbur may successively choose indices 1, 2, 3, 4, and 5, and add 1 to corresponding suffixes.
     66 
     67 In the second sample, Wilbur first chooses indices 1 and 2 and adds 1 to corresponding suffixes, then he chooses index 4 and subtract 1.