Submission #1244952

---

Source Code Expand

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
using namespace std;

int main(){
    long long n;
    cin >> n;

    long long a[100005];
    rep(i,n){
        cin >> a[i];
    }

    long long dp[100005];
    rep(i,100005) dp[i] = 1000000000;
    dp[0] = 0;
    rep(i,n - 1){
        long long dist = a[i] - a[i + 1];
        if(dist < 0) dist *= -1;

        if(dp[i] + dist < dp[i + 1]){
            dp[i + 1] = dp[i] + dist;
        }

        if(i == n - 2) break;
        dist = a[i] - a[i + 2];
        if(dist < 0) dist *= -1;

        if(dp[i] + dist < dp[i + 2]){
            dp[i + 2] = dp[i] + dist;
        }
    }
    cout << dp[n - 1] << endl;
}

Submission Info

Judge Result