Pagini recente » Cod sursa (job #1626696) | Cod sursa (job #950677) | Cod sursa (job #2984261) | Cod sursa (job #3129951) | Cod sursa (job #119114)
Cod sursa(job #119114)
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;
i:=0;
i2:=n;
while (i<n) and (j<=c) 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;
i:=i+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
begin
mc[i]:=0;
st[i]:=0;
for j:=1 to n do
if st2[j]=0 then
mc[i]:=mc[i]+mat[i,j]
end;
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
i:=0;
j:=0;
i2:=m;
while (i<m) and (j<=r) 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;
i:=i+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
begin
ml[j]:=0;
st2[j]:=0;
for i:=1 to m do
if st[i]=0 then
ml[j]:=ml[j]+mat[i,j]
end;
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.