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.

Download