Pagini recente » Cod sursa (job #315835) | Cod sursa (job #2895048) | Cod sursa (job #1496229) | Cod sursa (job #99655) | Cod sursa (job #32208)
Cod sursa(job #32208)
using namespace std;
#include<fstream>
#include<stdio.h>
int a[550][17],sl[550],sc[17];
int m,n,r,c;
int nr1(int x,int col)
{
int i,j=0;
for(i=1;i<(1<<n);i<<=1)
if(i&x)
j++;
if(j==col)
return 1;
return 0;
}
int main()
{
FILE *fin=fopen("elimin.in","r"),
*fout=fopen("elimin.out","w");
fscanf(fin,"%d%d%d%d",&m,&n,&r,&c);
int i,j,inv=0,k,totl[550];
if(m<n)
{
inv=1;
m^=n;
n^=m;
m^=n;
r^=c;
c^=r;
r^=c;
for(j=1;j<=n;j++)
for(i=1;i<=m;i++)
fscanf(fin,"%d",&a[i][j]);
}
else
{
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
fscanf(fin,"%d",&a[i][j]);
}
int sol=-1,crt,tot=0;
int x=0;
memset(totl,0,sizeof totl);
memset(sc,0,sizeof sc);
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
tot+=a[i][j];
sc[j]+=a[i][j];
totl[i]+=a[i][j];
}
for(x=0;x<(1<<n);x++)
if(nr1(x,c))
{
crt=tot;
for(i=0;i<n;i++)
if(x&(1<<i))
crt-=sc[i+1];
for(i=1;i<=m;i++)
sl[i]=totl[i];
for(j=1;j<=n;j++)
if((1<<(j-1))&x)
for(i=1;i<=m;i++)
sl[i]-=a[i][j];
for(i=1;i<=m;i++)
{
j=i;
while(j/2&&sl[j/2]<sl[j])
{
sl[j/2]^=sl[j];
sl[j]^=sl[j/2];
sl[j/2]^=sl[j];
j/=2;
}
}
i=m;
while(i>1)
{
sl[i]^=sl[1];
sl[1]^=sl[i];
sl[i]^=sl[1];
i--;
j=1;
while(1)
{
k=2*j;
if(k>i) break;
if(k+1<=i&&sl[k+1]>sl[k]) k++;
if(sl[k]<sl[j]) break;
sl[k]^=sl[j];
sl[j]^=sl[k];
sl[k]^=sl[j];
j=k;
}
}
for(i=1;i<=r;i++)
crt-=sl[i];
if(crt>sol)
sol=crt;
}
fprintf(fout,"%d\n",sol);
fclose(fin);
fclose(fout);
return 0;
}