Cod sursa(job #14527)

Utilizator CezarMocanCezar Mocan CezarMocan Data 9 februarie 2007 11:53:29
Problema Elimin Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 3.5 kb
var s,st:array[0..25]of longint;
    v:array[0..20,0..7500]of longint;
    x:array[0..800]of longint;
    i,j,n,m,r,c,stot,max,aux:longint;

{procedure qsort(ls,ld:longint);
var i,j,aux:longint;
begin
  i:=ls;j:=ld;
  while true do begin
    while (x[i]<=x[j])and(i<>j) do inc(i);
    if i=j then break;
    aux:=x[i];x[i]:=x[j];x[j]:=aux;dec(j);
    while (x[i]<=x[j])and(i<>j) do dec(j);
    if i=j then break;
    aux:=x[i];x[i]:=x[j];x[j]:=aux;inc(i);
  end;
  if j-1>ls then qsort(ls,j-1);
  if j+1<ld then qsort(j+1,ld);
end;}

Procedure QSort(left : Integer; right : Integer);
Var pivot, l_ptr, r_ptr : Integer;
Begin
 randomize;
 l_ptr := left;
 r_ptr := right;
 pivot := x[random(n)+1];
 While (left < right) do
  Begin
   While ((x[right] >= pivot) AND (left < right)) do
    right := right - 1;
   If (left <> right) then
    Begin
     x[left] := x[right];
     left := left + 1;
    End;
   While ((x[left] <= pivot) AND (left < right)) do
    left := left + 1;
   If (left <> right) then
    Begin
     x[right] := x[left];
     right := right - 1;
    End;
  End;
 x[left] := pivot;
 pivot := left;
 left := l_ptr;
 right := r_ptr;
 If (left < pivot) then
  QSort(left, pivot-1);
 If (right > pivot) then
  QSort(pivot+1, right);
End;

procedure back(k,no:longint);
var i,j,ss,min,nr:longint;
    ok:boolean;
begin
if k=no then
        begin
        nr:=0;
        for i:=1 to no do
                if st[i]=1 then
                        begin
                        inc(nr);
                        s[nr]:=i;
                        end;
        if nr=r then
                begin
                ss:=stot;
                for i:=1 to n do
                        x[i]:=v[0,i];
                for i:=1 to nr do
                        for j:=1 to n do
                                dec(x[j],v[s[i],j]);
                for i:=1 to nr do
                        ss:=ss-v[s[i],0];
                for i:=1 to n-1 do
                        if x[i]<x[i+1] then
                                begin
                                aux:=x[i];
                                x[i]:=x[i+1];
                                x[i+1]:=aux;
                                end;
                qsort(1,n);
                for i:=1 to c do
                        ss:=ss-x[i];
                if ss>max then
                        max:=ss;
                end
        end
else
        for i:=1 downto 0 do
                begin
                st[k+1]:=i;
                back(k+1,no);
                end;
end;

begin
assign(input,'elimin.in');reset(input);
assign(output,'elimin.out');rewrite(output);
readln(m,n,r,c);
if n<m then
        begin
        aux:=n;
        n:=m;
        m:=aux;
        aux:=r;
        r:=c;
        c:=aux;
        for i:=1 to n do
                for j:=1 to m do
                        begin
                        read(v[j,i]);
                        inc(v[j,0],v[j,i]);
                        stot:=stot+v[j,i];
                        end;
        for i:=1 to m do
                for j:=1 to n do
                        inc(v[0,j],v[i,j]);
        end
else begin
for i:=1 to m do
        for j:=1 to n do
                begin
                read(v[i,j]);
                inc(v[i,0],v[i,j]);
                stot:=stot+v[i,j];
                end;
for i:=1 to n do
        for j:=1 to m do
                inc(v[0,i],v[j,i]);
end;
back(0,m);
writeln(max);
close(input);close(output);
end.