Cod sursa(job #137496)

Utilizator h_istvanHevele Istvan h_istvan Data 17 februarie 2008 12:27:30
Problema Stalpi Scor 20
Compilator fpc Status done
Runda preONI 2008, Runda 4, Clasele 11-12 Marime 1.74 kb
program stalpi;
type stalp = record
             x,s,d,c:longint;
             end;
var f:text;
    n,i,j:longint;
    v:array[1..100000] of stalp;
    a,b:array[1..100000] of extended;

procedure qsort(bal,jobb:longint);
var i,j,va:longint;
    cs:stalp;
begin
     i:=bal;j:=jobb;
     va:=v[(i+j) div 2].x;
     while (i<=j) do
     begin
          while(v[i].x < va) do inc(i);
          while(v[j].x > va) do dec(j);
          if(i<=j) then
          begin
               cs:=v[i];
               v[i]:=v[j];
               v[j]:=cs;
               inc(i);dec(j);
          end;
     end;
     if(bal<j) then qsort(bal,j);
     if(i<jobb) then qsort(i,jobb);
end;

function jobbra(x:longint):longint;
var i:longint;
begin
     i:=x;
     while(v[x].d+v[x].x >= v[i].x) and (i<=n) do inc(i);
     jobbra:=i-x-1;
end;

function balra(x:longint):longint;
var i:longint;
begin
     i:=x;
     while(v[x].x-v[x].s <= v[i].x) and (i>0) do dec(i);
     balra:=x-i-1;
end;

begin
     assign(f,'stalpi.in');
     reset(f);
     readln(f,n);
     for i:=1 to n do
         readln(f,v[i].x,v[i].c,v[i].s,v[i].d);
     close(f);

     qsort(1,n);

     for i:=1 to n do
     begin
          v[i].s:=balra(i);
          v[i].d:=jobbra(i);
     end;

     for i:=1 to n do
     begin
          a[i]:=v[i].c;
          if(i-v[i].s-1 > 0) then a[i]:=a[i]+b[i-v[i].s-1];
          if(a[i] < b[i]) or (b[i] = 0) then b[i]:=a[i];
          for j:=i-v[i].s to i-1 do
              if (a[i] < b[j]) then b[j]:=a[i];
          for j:=i+1 to i+v[i].d do
              if (b[j] = 0) or (a[i] < b[j]) then b[j]:=a[i];
     end;

     assign(f,'stalpi.out');
     rewrite(f);
     writeln(f,b[n]:0:0);
     close(f);
end.