PROG-1108 : สายแร่แห่งพลัง 2 (ore2) (Deque)

#include <bits/stdc++.h>

using namespace std;
using lli = long long;
using pli = pair <lli, int>;
const int N = 1e6 + 10;
lli qs[N], dp[N];

int main(){

    int n, k;
    scanf("%d %d", &n, &k);

    for(int i=1;i<=n;i++){
        scanf("%lld", &qs[i]);
        qs[i] += qs[i - 1];
    }

    deque <pli> dq; /// (-qs[i] + dp[i - 1], i)
    dq.push_back({0, 0});
    dp[1] = qs[1] > k ? 0: qs[1];

    for(int i=2;i<=n;i++){
        lli cur = -qs[i - 1] + dp[i - 2];
        while(!dq.empty() and cur >= dq.back().first)
            dq.pop_back();
        dq.push_back({cur, i - 1});

        while(!dq.empty() and qs[i] - qs[dq.front().second] > k)
            dq.pop_front();

        if(dq.size() == 0) dp[i] = dp[i - 1];
        else dp[i] = max(dp[i - 1], qs[i] + dq.front().first);
    }

    printf("%lld", dp[n]);

    return 0;
}