#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<set>
#define see(x) cout<<#x<<":"<<x<<endl;
using namespace std;
const int maxn = 100005;
long long dp[maxn], a[maxn];
int q[maxn];
multiset<long long> Set;
int main(){
    int n, i, j, k, low, ok, l, r;
    long long sum, m, tmp;
    while(scanf("%d%lld",&n,&m)!=-1){//这里写成多case就wa了，去掉之后就A了，无语了
        sum = 0; low = 1;
        l = 0; r = -1;
        Set.clear();
        dp[0] = 0; ok = 1;
        for(i=1;i<=n;i++){
            scanf("%lld",&a[i]);
            sum += a[i];
            while(sum>m) sum -= a[low++];
            if(low>i){
                ok = 0;break;
            }
            while(l<=r&&a[i]>=a[q[r]]){
                if(l<r)
                    Set.erase(dp[q[r-1]]+a[q[r]]);
                r--;
            }
            q[++r] = i;
            if(l<r) Set.insert(dp[q[r-1]]+a[q[r]]);
            while(low>q[l]){
                if(l<r)
                    Set.erase(dp[q[l]]+a[q[l+1]]);
                l++;
            }
            tmp = *(Set.begin());
            dp[i] = dp[low-1]+a[q[l]];
            if(l<r&&dp[i]>tmp) dp[i] = tmp;
        }
        if(ok){
            printf("%lld\n",dp[n]);
        }
        else{
            printf("-1\n");
        }
    }
    return 0;
}

• 果然！！！ (1470) wccy 2012-10-06 10:44:30