提出 #44024119

---

ソースコード 拡げる

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
using ll = long long int;
using Data = pair<ll, int>;
const ll INF = 1LL << 60;

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

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

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

    priority_queue<Data> que_max;
    priority_queue<Data> que_min;
    vector<ll> dp(N + 1, -INF);
    dp[0] = 0;
    for(int i=0; i<N; i++) {
        // 最大値を取る
        while (!que_max.empty()) {
            auto [val, end_idx] = que_max.top();
            if (i < end_idx) {
                dp[i+1] = max(dp[i+1], val - A[i]);
                break;
            } else {
                que_max.pop();
            }
        }
        while (!que_min.empty()) {
            auto [val, end_idx] = que_min.top();
            if (i < end_idx) {
                dp[i+1] = max(dp[i+1], val + A[i]);
                break;
            } else {
                que_min.pop();
            }
        }

        // 使わない
        dp[i+1] = max(dp[i+1], dp[i]);
        // max として使う
        que_max.emplace(dp[i] + A[i], next_big[i] + 1);
        // min として使う
        que_min.emplace(dp[i] - A[i], next_small[i] + 1);
    }
    cout << dp[N] << endl;
    return 0;
}

提出情報

ジャッジ結果