提出 #44024750

---

ソースコード 拡げる

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <atcoder/segtree>
using namespace atcoder;
using namespace std;
using ll = long long int;
const ll INF = 1LL << 60;

ll op_max(ll a, ll b) {
    return max(a, b);
}

ll e() {
    return -INF;
}

int main() {
    int N; cin >> N;
    vector<ll> A(N);
    for(int i=0; i<N; i++) {
        cin >> A[i];
    }

    vector<int> lim1(N), lim2(N);
    stack< pair<ll, int> > st;

    // k < i かつ A[k] >= A[i] を満たす最大の添字を探す
    st.emplace(INF, 0);
    for(int i=0; i<N; i++) {
        while(st.top().first < A[i]) st.pop();
        lim1[i] = st.top().second;
        st.emplace(A[i], i + 1);
    }
    st.pop();

    // k < i かつ A[k] <= A[i] を満たす最大の添字を探す
    st.emplace(-INF, 0);
    for(int i=0; i<N; i++) {
        while(st.top().first > A[i]) st.pop();
        lim2[i] = st.top().second;
        st.emplace(A[i], i + 1);
    }

    segtree<ll, op_max, e> seg1(N+1);
    segtree<ll, op_max, e> seg2(N+1);
    seg1.set(0, -A[0]);
    seg2.set(0, +A[0]);

    vector<ll> dp(N+1, -INF);
    dp[0] = 0;
    for(int i=0; i<N; i++) {
        // 部分列に含めない場合
        dp[i+1] = max(dp[i+1], dp[i]);
        // 部分列の最大値として使う場合
        ll v1 = seg1.prod(lim1[i], i);
        dp[i+1] = max(dp[i+1], v1 + A[i]);
        // 部分列の最小値として使う場合
        ll v2 = seg2.prod(lim2[i], i);
        dp[i+1] = max(dp[i+1], v2 - A[i]);
        if (i + 1 < N) {
            seg1.set(i+1, dp[i+1] - A[i+1]);
            seg2.set(i+1, dp[i+1] + A[i+1]);
        }
    }
    cout << dp[N] << endl;
    return 0;
}

提出情報

ジャッジ結果