NKMAXSEQ - Dãy con dài nhất
Tác giả: ladpro98
Ngôn ngữ: Pascal
program nkmaxseq;
uses math;
const fi='';
maxN=50005;
var a,s,mins:array[0..maxN] of longint;
n,res,p:longint;
procedure input;
var f:text;
i:longint;
begin
assign(f,fi);
reset(f);
readln(f,n,p);
for i:=1 to n do
readln(f,a[i]);
close(f);
end;
procedure init;
var i,m:longint;
begin
minS[0]:=0;
s[1]:=a[1];
for i:=2 to n do
s[i]:=s[i-1]+a[i];
m:=s[1];
for i:=1 to n do
mins[i]:=min(mins[i-1],s[i]);
end;
function find(r,key:longint):longint;
var l,m,k:longint;
begin
l:=0;
k:=n+1;
while l<=r do
begin
m:=(l+r) shr 1;
if mins[m]<=key then
begin
k:=m;
r:=m-1;;
end
else l:=m+1;
end;
exit(k);
end;
procedure process;
var i,pos:longint;
begin
for i:=2 to n do
begin
pos:=find(i,s[i]-p);
if pos<>n+1 then
res:=max(res,i-pos);
end;
end;
begin
input;
init;
process;
if res=0 then res:=-1;
write(res);
end.