LEM5 - ARITHMETIC PROGRESSION

Tác giả: RR

Ngôn ngữ: Pascal

{$R+,Q+}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=100001;
  hashkey=100003;
type
  list=^node;
  node=record
         u:longint;
         next:list;
       end;
var
  f1,f2:text;
  kq,n:longint;
  a:array[1..MAXN] of longint;
  h:array[0..hashkey] of list;
  d:array[1..MAXN,1..100] of longint;
procedure openF; inline;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF; inline;
begin
  close(f1); close(f2);
end;
procedure inp; inline;
var
  i:longint;
begin
  read(f1,n);
  for i:=1 to n do
    read(f1,a[i]);
end;
function find(x:longint):longint; inline;
var
  p:list;
  u:longint;
begin
  p:=h[abs(x) mod hashkey];
  while p<>nil do
    begin
      u:=p^.u; p:=p^.next;
      if a[u]=x then exit(u);
    end;
  exit(0);
end;
procedure push(x:longint); inline;
var
  p:list;
  u,gt:longint;
begin
  gt:=abs(a[x]) mod hashkey;
  p:=h[gt];
  while p<>nil do
    begin
      u:=p^.u;
      if a[u]=a[x] then begin p^.u:=x; exit; end;
      p:=p^.next;
    end;
  new(p); p^.u:=x; p^.next:=h[gt]; h[gt]:=p;
end;
procedure solve; inline;
var
  i,csc,k:longint;
begin
  kq:=1;
  for csc:=1 to 100 do d[1,csc]:=1;
  push(1);
  for i:=2 to n do
    for csc:=1 to 100 do
      begin
        k:=find(a[i]-csc);
        if k>0 then d[i,csc]:=d[k,csc]+1
        else d[i,csc]:=1;
        push(i);
        kq:=max(kq,d[i,csc]);
      end;
end;
procedure ans; inline;
begin
  writeln(f2,kq);
end;
begin
  openF;
  inp;
  solve;
  ans;
  closeF;
end.

Download