Cod sursa(job #85262)

Utilizator gurneySachelarie Bogdan gurney Data 20 septembrie 2007 18:15:36
Problema Tribute Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.32 kb
program tribute;
  const
    fin='tribute.in';
    fout='tribute.out';
    nmax=50000;
  var
    min2,nro,nlo,poz,l,s2,r,s,nr,nl,k,nx,ny,n,i,j,xmin,ymin,min:longint;
    x,y,b,c:array[-1..nmax] of longint;
begin
  assign(input,fin);assign(output,fout);
    reset(input);rewrite(output);
    readln(n,nx,ny);
    for i:=1 to n do
      readln(x[i],y[i]);
    //determinarea lui xmin
    fillchar(b,sizeof(b),0);
    for i:=1 to n do
      inc(b[x[i]]);
    for i:=0 to nmax do
      inc(b[i],b[i-1]);
    for i:=n downto 1 do
      begin
        c[b[x[i]]]:=x[i];
        dec(b[x[i]]);
      end;
    i:=1;
    l:=1;
    j:=1;
    while (nx>=c[j])and(j<=n) do
      inc(j);
    r:=j;
    s:=0;
    for i:=1 to n do
      if c[i]>nx then
        inc(s,c[i]-nx);
    nr:=n-j+1;
    min:=s;
    xmin:=0;
    poz:=0;
    nl:=0;
    while r<n+1 do
      begin
        inc(poz);
        nro:=nr;
        while (c[l]<poz) and (l<=n) do
          begin
            inc(l);
            inc(nl);
          end;
        while (c[r]<=poz+nx)and(r<=n) do
          begin
            inc(r);
            dec(nro);
          end;
        inc(s,nl);
        dec(s,nr);
        nr:=nro;
        if s<min then
          begin
            xmin:=poz;
            min:=s;
          end;
      end;
    //determinarea lui ymin
    fillchar(b,sizeof(b),0);
    for i:=1 to n do
      inc(b[y[i]]);
    for i:=0 to nmax do
      inc(b[i],b[i-1]);
    for i:=n downto 1 do
      begin
        c[b[y[i]]]:=y[i];
        dec(b[y[i]]);
      end;
    i:=1;
    l:=1;
    j:=1;
    while (ny>=c[j])and(j<=n) do
      inc(j);
    r:=j;
    s2:=0;
    for i:=1 to n do
      if c[i]>ny then
        inc(s2,c[i]-ny);
    nr:=n-j+1;
    min2:=s2;
    ymin:=0;
    poz:=0;
    nl:=0;
    while r<n+1 do
      begin
        inc(poz);
        nro:=nr;
        while (c[l]<poz) and (l<=n) do
          begin
            inc(l);
            inc(nl);
          end;
        while (c[r]<=poz+ny)and(r<=n) do
          begin
            inc(r);
            dec(nro);
          end;
        inc(s2,nl);
        dec(s2,nr);
        nr:=nro;
        if s2<min2 then
          begin
            ymin:=poz;
            min2:=s2;
          end;
      end;
    writeln(min+min2);
  close(input);close(output);
end.