LEM5 - ARITHMETIC PROGRESSION

Tác giả: flashmt

Ngôn ngữ: Pascal

uses math;
const fi='';
      maxn=100010;
var n,i,re,nn:longint;
    a,b,l,r,d,c:array[0..maxn] of longint;
    f:array[1..maxn,1..100] of longint;

procedure sort(l,r:longint);
var i,j,x,y,t:longint;
begin
     i:=l; j:=r; x:=a[(i+j) shr 1]; t:=d[(i+j) shr 1];
     repeat
           while (a[i]<x) or ((a[i]=x) and (d[i]<t)) do inc(i);
           while (a[j]>x) or ((a[j]=x) and (d[j]>t)) do dec(j);
           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;
                inc(i); dec(j);
           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
     c[0]:=-maxlongint;
     for i:=1 to n do
     begin
          if a[i]>c[nn] then
          begin
               r[nn]:=i-1;
               inc(nn);
               c[nn]:=a[i];
               l[nn]:=i;
          end;
          b[d[i]]:=nn;
     end;
     r[nn]:=n;
end;

function bs(ll,rr,val:longint):longint;
var mid,i,l,r:longint;
begin
     bs:=0; l:=ll; r:=rr;
     while l<=r do
     begin
          mid:=(l+r) shr 1;
          if d[mid]<val then l:=mid+1
          else r:=mid-1;
     end;
     for i:=mid+1 downto mid-1 do
         if (i>=ll) and (i<=rr) and (d[i]<val) then exit(d[i]);
end;

procedure pr;
var i,j,dif,x,y:longint;
begin
     for i:=1 to n do
     begin
          x:=b[i];
          for j:=x-1 downto 1 do
          begin
               dif:=c[x]-c[j];
               if dif>100 then break
               else
               begin
                    y:=bs(l[j],r[j],i);
                    if y=0 then continue;
                    f[i,dif]:=max(f[i,dif],f[y,dif]+1);
                    re:=max(re,f[i,dif]);
               end;
          end;
     end;
end;

begin
     assign(input,fi); reset(input);
     read(n);
     for i:=1 to n do
     begin
          read(a[i]); d[i]:=i;
     end;
     sort(1,n);
     edit;
     pr;
     writeln(re+1);
     close(input);
end.

Download