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.

Download