Pagini recente » tema | Cod sursa (job #976114) | Cod sursa (job #1391757) | Cod sursa (job #486325)
Cod sursa(job #486325)
#include<cstdio>
#include<algorithm>
#define N 1<<13
using namespace std;
int maxs,n,m,r,c,nr1,v[N],a[N][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,s[N]={0};
for(int j=1;j<=m;j++)
for(int i=1;i<=n;i++)
s[j]+=a[i][j]*(1-v[i]);
sort(s+1,s+m+1);
for(int j=c+1;j<=m;j++)
st+=s[j];
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,s[N]={0};
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
s[i]+=a[i][j]*(1-v[j]);
sort(s+1,s+n+1);
for(int i=r+1;i<=n;i++)
st+=s[i];
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;
}