NKMAXSEQ - Dãy con dài nhất
Tác giả: ll931110
Ngôn ngữ: Pascal
program nkmaxseq;
const
input = '';
output = '';
maxn = 50000;
maxv = 1000000001;
var
a,s: array[0..maxn] of longint;
t: array[0..6 * maxn] of longint;
n,p,tmp,res: longint;
procedure init;
var
f: text;
i: longint;
begin
assign(f, input);
reset(f);
readln(f, n, p);
s[0] := 0;
for i := 1 to n do
begin
read(f, a[i]);
s[i] := s[i - 1] + a[i];
end;
close(f);
end;
procedure update(i,low,high,x: longint);
var
mid: longint;
begin
if low = high then
begin
t[i] := s[x];
exit;
end;
mid := (low + high) div 2;
if x <= mid then update(2 * i,low,mid,x)
else update(2 * i + 1,mid + 1,high,x);
if t[2 * i] > t[2 * i + 1] then t[i] := t[2 * i + 1] else t[i] := t[2 * i];
end;
procedure find(i,low,high,x: longint);
var
mid: longint;
begin
if t[i] > x then exit;
if low = high then
begin
tmp := low;
exit;
end;
mid := (low + high) div 2;
if t[2 * i] <= x then find(2 * i,low,mid,x)
else find(2 * i + 1,mid + 1,high,x);
end;
procedure solve;
var
i: longint;
begin
for i := 0 to 4 * maxn do t[i] := maxv;
update(1,0,n,0);
for i := 1 to n do
begin
tmp := -1;
find(1,0,n,s[i] - p);
if (tmp <> -1) and (res < i - tmp) then res := i - tmp;
update(1,0,n,i);
end;
end;
procedure printresult;
var
f: text;
begin
assign(f, output);
rewrite(f);
if res = 0 then writeln(f, -1) else writeln(f, res);
close(f);
end;
begin
init;
solve;
printresult;
end.