Cod sursa(job #70489)

Utilizator mlazariLazari Mihai mlazari Data 6 iulie 2007 09:34:24
Problema Secventa Scor 70
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.29 kb
Program Secventa;
const patr : array[0..18] of longint=(1,2,4,8,16,32,64,128,256,512,1024,2048,
                                  4096,8192,16384,32768,65536,131072,262144);
var k,n,s : longint;
    bmax,i2 : integer;
    A,M : array[1..500000] of integer;

procedure Citeste;
var Intrare : text;
    i : longint;
begin
  assign(Intrare,'secventa.in');
  reset(Intrare);
  readln(Intrare,n,k);
  for i:=1 to n do
   begin
     read(Intrare,A[i]);
     M[i]:=A[i];
   end;
  close(Intrare);
end;

function min(a,b : integer) : integer;
begin
  if a<b then min:=a else min:=b;
end;

function baza(s : longint) : integer;
begin
  if s<=n-patr[i2] then baza:=min(M[s],M[s+k-patr[i2]])
   else baza:=M[s];
end;

procedure Calculeaza;
var i : longint;
    b : integer;
begin
  i2:=0;
  while k>2*patr[i2] do
   begin
     for i:=1 to n-patr[i2] do M[i]:=min(M[i],M[i+patr[i2]]);
     i2:=i2+1;
   end;
  bmax:=-30001;
  for i:=1 to n-k+1 do
   begin
     b:=baza(i);
     if b>bmax then
      begin
        s:=i;
        bmax:=b;
      end;
   end;
end;

procedure Scrie;
var Iesire : text;
begin
  assign(Iesire,'secventa.out');
  rewrite(Iesire);
  write(Iesire,s,' ',s+k-1,' ',bmax);
  close(Iesire);
end;

begin
  Citeste;
  Calculeaza;
  Scrie;
end.