Cod sursa(job #119080)

Utilizator mari_anaMariana Gheorghe mari_ana Data 29 decembrie 2007 13:31:58
Problema Elimin Scor 70
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.39 kb
program elimin;
var m,n,r,c,i,j:integer;
    f:text;
    sol:int64;
    mc,ml:array[1..521] of int64;
    mat:array [1..521,1..521] of integer;
    st,st2:array [1..521] of integer;

procedure coloana;
var ind,limita:int64;

function ok(x:int64):boolean;
var mask:int64;
    j,i2:integer;
begin
j:=0;
i2:=n;
for i:=0 to (n-1) do
  begin
  mask:=1 shl i;
  if (x and mask)=mask then
  	begin
    j:=j+1;
    st2[i2]:=1
    end
  else
    st2[i2]:=0;
  i2:=i2-1
  end;
if j=c then
  ok:=true
else
  ok:=false
end;

function minim:integer;
var i:integer;
    min:int64;
begin
min:=1 shl 60;
for i:=1 to m do
  if (st[i]=0) and (mc[i]<min) then
    begin
    minim:=i;
    min:=mc[i]
    end
end;


procedure solutie;
var s:int64;
begin
for i:=1 to m do
  mc[i]:=0;
for i:=1 to m do
  for j:=1 to n do
    if st2[j]=0 then
      mc[i]:=mc[i]+mat[i,j];
for i:=1 to m do
  st[i]:=0;
for i:=1 to r do
  st[minim]:=1;

s:=0;
for i:=1 to m do
  if st[i]=0 then
    s:=s+mc[i];
if s>sol then
  sol:=s
end;

begin
limita:=(1 shl n)-1;
ind:=0;
while ind<=limita do
	begin
  if ok(ind) then
    solutie;
  ind:=ind+1
  end
end;

procedure linie;
var ind,limita:int64;

function ok(x:int64):boolean;
var mask:int64;
    j,i2:integer;
begin
j:=0;
i2:=m;
for i:=0 to (m-1) do
  begin
  mask:=1 shl i;
  if (x and mask)=mask then
  	begin
    j:=j+1;
    st[i2]:=1
    end
  else
    st[i2]:=0;
  i2:=i2-1
  end;
if j=r then
  ok:=true
else
  ok:=false
end;

function minim:integer;
var j:integer;
    min:int64;
begin
min:=1 shl 60;
for j:=1 to n do
  if (st2[j]=0) and (ml[j]<min) then
    begin
    minim:=j;
    min:=ml[j]
    end
end;


procedure solutie;
var s:int64;
begin
for j:=1 to n do
  ml[j]:=0;
for j:=1 to n do
  for i:=1 to m do
    if st[i]=0 then
      ml[j]:=ml[j]+mat[i,j];
for j:=1 to n do
  st2[j]:=0;
for j:=1 to c do
  st2[minim]:=1;

s:=0;
for j:=1 to n do
  if st2[j]=0 then
    s:=s+ml[j];
if s>sol then
  sol:=s
end;

begin
limita:=(1 shl m)-1;
ind:=0;
while ind<=limita do
	begin
  if ok(ind) then
    solutie;
  ind:=ind+1
  end
end;



begin
assign(f,'elimin.in'); reset(f);
readln(f,m,n,r,c);
for i:=1 to m do
  for j:=1 to n do
    read(f,mat[i,j]);
sol:=0;
if m<n then
  linie
else
  coloana;
assign(f,'elimin.out'); rewrite(f);
writeln(f,sol);
close(f)
end.