神题。比较难想的单调队列优化。暴力o(N^2)过掉。据说线段树(n*logN)会挂掉。。需要用到BST。额。。。惭愧了。贴出代码先。
#include <stdio.h>
int N;
__int64 M;
int data[100100];
__int64 sum[100100];
int queue[100100],qhead,qtail;
__int64 res[100100];
__int64 min(__int64 a,__int64 b)
{
if(a > b)
return b;
return a;
}
int main()
{
int i,j;
while(scanf("%d%I64d",&N,&M)!=EOF)
{
int OK = 1;
for(i=1;i<=N;i++)
{
scanf("%d",&data[i]);
if(data[i] > M)
OK = 0;
sum[i] = sum[i-1] + data[i];
}
qhead = qtail = 0;
int st = 1;
for(i=1;i<=N;i++)
{
while(qhead != qtail && data[i] > data[queue[qhead-1]])
qhead--;
queue[qhead++] = i;
while(sum[i] - sum[st-1] > M)
st++;
//[st,i] <=M
while(qhead != qtail && queue[qtail] < st)
qtail++;
res[i] = res[st-1] + data[queue[qtail]];
for(j=qtail;j<qhead-1;j++)
{
res[i] = min(res[i],res[queue[j]] + data[queue[j+1]] );
}
}
if(OK == 1)
printf("%I64d\n",res[N]);
else
printf("-1\n");
}
return 0;
}