Cod sursa(job #32192)

Utilizator floringh06Florin Ghesu floringh06 Data 17 martie 2007 14:25:31
Problema Elimin Scor 10
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.82 kb
type matrix = array[1..500,1..500] of integer;
     vect = array[1..500] of integer;

var fi,fo:text;
    n,m,r,c,i,j,aux:integer;
    sum,max:longint;
    a:matrix;
    v,vl:vect;

 procedure part(st,dr:integer; var stst,stdr,drst,drdr:integer);
  var i,j,aux,piv:longint;
   begin
    piv:=vl[(st+dr) div 2];
    i:=st-1;
    j:=dr+1;
    while i<j do
     begin
      repeat inc(i) until vl[i]<=piv;
      repeat dec(j) until vl[j]>=piv;
      if i<j then
       begin
        aux:=vl[i];
        vl[i]:=vl[j];
        vl[j]:=aux;
       end;
     end;
     stst:=st; drdr:=dr;
     if i=j then
      begin stdr:=j-1; drst:=i+1; end
     else
      begin stdr:=j; drst:=i; end;
    end;

  procedure sort(st,dr:integer);
   var stst,stdr,drst,drdr:integer;
    begin
     if st<dr then
      begin
       part(st,dr,stst,stdr,drst,drdr);
       sort(stst,stdr);
       sort(drst,drdr);
      end;
    end;


 procedure gosolve;
  var jj,ct:integer;
   begin
      for j:=1 to m do
       for i:=1 to n do
        inc(v[j],a[i,j]);
      for i:=0 to (1 shl n) do
       begin
        ct:=0;
        sum:=0;
        vl:=v;
        for j:=1 to n do
         if (i and (1 shl (j-1)))<>0 then  begin
           for jj:=1 to m do
            dec(vl[jj],a[j,jj]);  inc(ct); end;
         if ct=c then
          begin
           sort(1,m);
           for jj:=1 to m-c do
            inc(sum,vl[jj]);
           if sum>max then max:=sum;
          end;
       end;
   end;

begin
 assign(fi,'elimin.in'); reset(fi);
 assign(fo,'elimin.out'); rewrite(fo);
 readln(fi,n,m,r,c);
 for i:=1 to n do
  for j:=1 to m do
    read(fi,a[i,j]);
 if m<n then
  begin
   aux:=n;
   n:=m;
   m:=n;
   aux:=r;
   r:=c;
   c:=aux;
  end;
 gosolve;
 writeln(fo,max);
close(fi);
close(fo);
end.