Pagini recente » Istoria paginii runda/vvvvvv | Cod sursa (job #2431881) | Cod sursa (job #1611016) | Cod sursa (job #2471051) | Cod sursa (job #486330)
Cod sursa(job #486330)
#include<cstdio>
#define N 1<<12
int maxs,n,m,r,c,nr1,v[N],a[N][N],s[N],used[N];
void read()
{
freopen("elimin.in","r",stdin);
freopen("elimin.out","w",stdout);
scanf("%d%d%d%d",&n,&m,&r,&c);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
}
void makesuml()
{
int st=0,nrt=0;
for(int i=0;i<N;i++)
s[i]=used[i]=0;
for(int j=1;j<=m;j++)
for(int i=1;i<=n;i++)
s[j]+=a[i][j]*(1-v[i]);
do
{
nrt++;
int min=1<<30,pmin=0;
for(int i=1;i<=n;i++)
if(s[i]<min && !used[i])
min=s[i],pmin=i;
used[pmin]=1;
st-=min;
}
while(nrt<c);
if(st>maxs)
maxs=st;
}
void backl(int poz)
{
if(poz==n+1)
{
if(nr1==r)
makesuml();
return;
}
v[poz]=0;
backl(poz+1);
if(nr1<r)
{
v[poz]=1;
nr1++;
backl(poz+1);
nr1--;
}
}
void makesumc()
{
int st=0,nrt=0;
for(int i=0;i<N;i++)
s[i]=used[i]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
s[i]+=a[i][j]*(1-v[j]);
for(int i=1;i<=n;i++)
st+=s[i];
do
{
nrt++;
int min=1<<30,pmin=0;
for(int i=1;i<=n;i++)
if(s[i]<min && !used[i])
min=s[i],pmin=i;
used[pmin]=1;
st-=min;
}
while(nrt<r);
if(st>maxs)
maxs=st;
}
void backc(int poz)
{
if(poz==m+1)
{
if(nr1==c)
makesumc();
return;
}
v[poz]=0;
backc(poz+1);
if(nr1<c)
{
v[poz]=1;
nr1++;
backc(poz+1);
nr1--;
}
}
void solve()
{
maxs=-1;
if(n<m)
backl(1);
else
backc(1);
printf("%d",maxs);
}
int main()
{
read();
solve();
return 0;
}