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.

Download