NKMAXSEQ - Dãy con dài nhất
Tác giả: RR
Ngôn ngữ: Pascal
uses math;
const
MAXN=50111;
var
i,n,p:longint;
a,sum,ind:array[0..MAXN] of longint;
procedure swap(var a,b:longint);
var
tmp:longint;
begin
tmp:=a; a:=b; b:=tmp;
end;
procedure sort(l,r:longint);
var
i,j,ms,mi,key:longint;
begin
i:=l; j:=r;
key:=l+random(r-l+1);
ms:=sum[key]; mi:=ind[key];
repeat
while (sum[i]<ms) or ((sum[i]=ms) and (ind[i]<mi)) do inc(i);
while (sum[j]>ms) or ((sum[j]=ms) and (ind[j]>mi)) do dec(j);
if i<=j then
begin
swap(sum[i],sum[j]);
swap(ind[i],ind[j]);
inc(i); dec(j);
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;
procedure solve;
var
i,j,nn,res:longint;
begin
j:=0; nn:=n+1; res:=0;
for i:=1 to n do
begin
while sum[j+1]<=sum[i]-p do
begin
inc(j);
nn:=min(nn,ind[j]);
end;
if nn<=ind[i] then res:=max(res,ind[i]-nn);
end;
if res=0 then res:=-1;
writeln(res);
end;
begin
read(n,p);
for i:=1 to n do
begin
read(a[i]);
sum[i]:=sum[i-1]+a[i];
ind[i]:=i;
end;
inc(n); ind[n]:=0; sum[n]:=0;
sort(1,n);
solve;
end.