/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 333 点
問題文
高橋君は山道をハイキングしている。山道には一列に並んだ N 個の地点があり、順に地点 1, 地点 2, \ldots, 地点 N と番号が付いている。地点 i の標高は A_i である。
高橋君は地点 1 から出発し、地点 N に到達したい。高橋君は地点番号が増加する方向にのみ進むことができ、地点 i にいるとき、地点 i + 1（i + 1 \leq N のとき）または地点 i + 2（i + 2 \leq N のとき）のいずれかに進むことができる。
地点 i から地点 i+1 または地点 i+2 に進むとき、移動先の地点の標高を A_j とすると、疲労が \max(A_j - A_i, 0) だけ加算される。すなわち、移動先の標高が現在地より高い場合はその標高差が疲労となり、そうでない場合は疲労の加算は 0 である。
高橋君が地点 1 から地点 N まで移動するときの、疲労の合計の最小値を求めてください。ただし、出発時の疲労は 0 とする。
制約
- 2 \leq N \leq 5 \times 10^5
- 0 \leq A_i \leq 10^9（1 \leq i \leq N）
- 入力はすべて整数である。
入力
N A_1 A_2 \cdots A_N
1 行目には、地点の数を表す整数 N が与えられる。2 行目には、各地点の標高を表す N 個の整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。
出力
高橋君が地点 1 から地点 N まで移動するために必要な疲労の合計の最小値を 1 行で出力せよ。
入力例 1
4 10 30 20 25
出力例 1
15
入力例 2
5 8 6 7 3 2
出力例 2
0
入力例 3
10 5 12 4 20 7 15 3 18 6 10
出力例 3
10
入力例 4
20 100 180 120 250 130 300 90 200 80 260 140 400 150 350 170 500 160 450 190 210
出力例 4
170
入力例 5
2 1000000000 0
出力例 5
0
Score : 333 pts
Problem Statement
Takahashi is hiking along a mountain trail. The trail has N points arranged in a line, numbered sequentially as point 1, point 2, \ldots, point N. The elevation of point i is A_i.
Takahashi starts at point 1 and wants to reach point N. He can only move in the direction of increasing point numbers. When he is at point i, he can move to either point i + 1 (if i + 1 \leq N) or point i + 2 (if i + 2 \leq N).
When moving from point i to point i+1 or point i+2, if the elevation of the destination point is A_j, then fatigue of \max(A_j - A_i, 0) is accumulated. In other words, if the destination's elevation is higher than the current location, the elevation difference becomes fatigue; otherwise, the fatigue added is 0.
Find the minimum total fatigue when Takahashi travels from point 1 to point N. The initial fatigue at departure is 0.
Constraints
- 2 \leq N \leq 5 \times 10^5
- 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
- All inputs are integers.
Input
N A_1 A_2 \cdots A_N
The first line contains an integer N representing the number of points. The second line contains N integers A_1, A_2, \ldots, A_N separated by spaces, representing the elevation of each point.
Output
Print on a single line the minimum total fatigue required for Takahashi to travel from point 1 to point N.
Sample Input 1
4 10 30 20 25
Sample Output 1
15
Sample Input 2
5 8 6 7 3 2
Sample Output 2
0
Sample Input 3
10 5 12 4 20 7 15 3 18 6 10
Sample Output 3
10
Sample Input 4
20 100 180 120 250 130 300 90 200 80 260 140 400 150 350 170 500 160 450 190 210
Sample Output 4
170
Sample Input 5
2 1000000000 0
Sample Output 5
0