Cod sursa(job #137555)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 17 februarie 2008 12:38:48
Problema Stalpi Scor 0
Compilator fpc Status done
Runda preONI 2008, Runda 4, Clasele 11-12 Marime 2.77 kb
type quatro=record
       S,D,C:longint;
     end;
     two=record
       lii,lff,css:longint;
     end;
const nmax=2000;
var fi,fo:text;
    n,i,j,x,cost,min,max,st,dr:longint;
    nr:array[1..nmax]of quatro;
    s:array[1..nmax]of byte;
    int:array[1..nmax]of two;
    ll:array[0..500000]of longint;
procedure heapsort(n:longint);
var i,j,k:longint;
    aux:quatro;
begin
  for i:=1 to n do
    begin
      j:=i;
      while (j shr 1<>0)and(nr[j shr 1].C<nr[j].C) do
        begin
          aux:=nr[j shr 1];
          nr[j shr 1]:=nr[j];
          nr[j]:=aux;
          j:=j shr 1;
        end;
    end;
  i:=n;
  while i>1 do
    begin
      aux:=nr[1];
      nr[1]:=nr[i];
      nr[i]:=aux;
      dec(i);
      j:=1;
      while (j>0) do
        begin
          k:=2*j;
          if (k>i) then break;
          if (k+1<=i)and(nr[k+1].C>nr[k].C) then inc(k);
          if nr[j].C>=nr[k].C then break;
          aux:=nr[j];
          nr[j]:=nr[k];
          nr[k]:=aux;
          j:=k;
        end;
    end;
end;
function verif(li,lf,ct:longint):longint;
var i:longint;
begin
  for i:=1 to ct do
    begin
      if (int[i].lii<=li)and(int[i].lff<=lf) then
        begin
          li:=int[i].lff+1;
          if li>lf then begin verif:=-1; exit; end end
      else
      if (li<=int[i].lii)and(lf<=int[i].lff) then
        begin
          lf:=int[i].lii-1;
          if li>lf then begin verif:=-1; exit; end; end
      else
      if (li>=int[i].lii)and(lf<=int[i].lff) then
        begin
          verif:=-1; exit; end;
    end;
  if ((li>=min)and(li<=max))or((lf>=min)and(lf<=max)) then verif:=-2;
end;
procedure solve;
var i,ct,aux,ctot,cc,ok:longint;
begin
  ct:=0;
  for i:=1 to n do
    begin
     aux:=verif(nr[i].S,nr[i].D,ct);
     if aux=-2 then
       begin
         inc(ct);
         int[ct].lii:=nr[i].S;
         int[ct].lff:=nr[i].D;
         int[ct].css:=nr[i].C;
       end;
     end;
  ctot:=0; cc:=0;
   for i:=1 to ct do
     if s[i]=0 then
       begin
         ok:=0;
         for j:=int[i].lii to int[i].lff do
           if (ll[j]=0)and(j>=min)and(j<=max) then
             begin
               ll[j]:=1;
               inc(cc);
               ok:=1;
             end;
         if ok=1 then ctot:=ctot+int[i].css;
         if cc=max-min+1 then
           begin
             writeln(fo,ctot);
             exit;
           end;
       end;
end;
begin
  assign(fi,'stalpi.in'); reset(fi);
  assign(fo,'stalpi.out'); rewrite(fo);
  read(fi,n);
  min:=1000000;
  max:=0;
  for i:=1 to n do
    begin
      read(fi,x,nr[i].C,st,dr);
      nr[i].S:=x-st;
      nr[i].D:=x+dr;
      if x<min then min:=x;
      if x>max then max:=x;
    end;
  heapsort(n);
  solve;
  close(fi);
  close(fo);
end.