PROG-T1108: Ore2

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

using lli = long long;
using pli = pair<lli, int>;

int main(){

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

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

    vector<lli> dp(n + 1, 0);
    deque<pli> q;
    q.push_back(make_pair(0, 0));
    for(int i = 1; i <= n; ++i){
        while(!q.empty() && q.back().first < dp[i - 1] - qs[i]){
            q.pop_back();
        }
        q.push_back(make_pair(dp[i - 1] - qs[i], i));
        while(!q.empty() && qs[i] - qs[q.front().second] > lim){
            q.pop_front();
        }
        dp[i] = qs[i] + q.front().first;
    }

    cout << dp[n];

    return 0;
}