Pagini recente » Cod sursa (job #1900733) | Cod sursa (job #2889217) | Istoria paginii utilizator/gogoasamare | Cod sursa (job #555613) | Cod sursa (job #486349)
Cod sursa(job #486349)
#include<cstdio>
#include<algorithm>
#define N 1<<12
using namespace std;
int maxs,n,m,r,c,nr1,v[N],a[N][N],s[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;
for(int i=0;i<=n && i<=m;i++)
s[i]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
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;
for(int i=0;i<=n && i<=m;i++)
s[i]=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;
}