NKMAXSEQ - Dãy con dài nhất

Tác giả: flashmt

Ngôn ngữ: Pascal

const fi='';
      fo='';
      maxn=50005;
var n,re,p,num:longint;
    a,d,max,b,e:array[0..maxn] of longint;

procedure rf;
var i,t:longint;
begin
     assign(input,fi); reset(input);
     read(n,p);
     a[0]:=0; d[0]:=0;
     for i:=1 to n do
     begin
          read(t);
          a[i]:=a[i-1]+t;
          d[i]:=i;
     end;
     close(input);
end;

procedure sort(l,r:longint);
var x,y,i,j,u:longint;
begin
     i:=l; j:=r; x:=a[(i+j) shr 1]; u:=d[(i+j) shr 1];
     repeat
           while (a[i]<x) or ((a[i]=x) and (d[i]>u)) do i:=i+1;
           while (a[j]>x) or ((a[j]=x) and (d[j]<u)) do j:=j-1;
           if i<=j then
           begin
                y:=a[i]; a[i]:=a[j]; a[j]:=y;
                y:=d[i]; d[i]:=d[j]; d[j]:=y;
                i:=i+1; j:=j-1;
           end;
     until i>j;
     if i<r then sort(i,r);
     if l<j then sort(l,j);
end;

procedure edit;
var i:longint;
begin
     num:=0; b[0]:=a[0]; e[0]:=d[0];
     for i:=1 to n do
         if a[i]<>b[num] then
         begin
              inc(num);
              b[num]:=a[i];
              e[num]:=d[i];
         end;
     max[num]:=e[num];
     for i:=num-1 downto 0 do
         if e[i]>max[i+1] then max[i]:=e[i]
         else max[i]:=max[i+1];
end;

function bs(x:longint):longint;
var l,r,m,j:longint;
begin
     l:=0; r:=num;
     while l<=r do
     begin
          m:=(l+r) shr 1;
          if b[m]=x then break;
          if b[m]<x then l:=m+1
          else r:=m-1;
     end;
     for j:=m-1 to m+1 do
         if (j>=0) and (j<=num) and (b[j]>=x) then break;
     bs:=j;
end;

procedure pr;
var i,t:longint;
begin
     sort(0,n);
     edit;
     re:=-1;
     for i:=0 to n do
     begin
          if a[i]+p>a[n] then break;
          if a[i]+p<a[0] then t:=0
          else
              if (i=0) or (a[i]<>a[i-1]) then t:=bs(a[i]+p);
          if max[t]-d[i]>re then re:=max[t]-d[i];
     end;
end;

procedure wf;
begin
     assign(output,fo); rewrite(output);
     writeln(re);
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Download