Pagini recente » Cod sursa (job #1891267) | Cod sursa (job #3003814) | Cod sursa (job #3212656) | Cod sursa (job #2164771) | Cod sursa (job #875025)
Cod sursa(job #875025)
#include<cstdio>
#include<algorithm>
#define nmax 500
using namespace std;
int a[nmax][nmax],n,m,r,c,sol,v[nmax];
void backL(int,int), backC(int,int);
int main()
{
int i,j;
freopen("elimin.in","r",stdin);
freopen("elimin.out","w",stdout);
scanf("%d%d%d%d", &m, &n, &r, &c);
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
scanf("%d", &a[i][j]);
if(r<c)
backL(1,0);
else
backC(1,0);
printf("%d ", sol);
return 0;
}
void backL(int k,int r1)
{
int i,j,s[nmax],S;
if(k>m+1)return;
if(r1>r)return;
if(r1==r&&k==m+1)
{
S=0;
for(i=1;i<=n;i++)s[i]=0;
for(j=1;j<=n;j++)
for(i=1;i<=m;i++)
s[j]+=a[i][j]*v[i];
sort(s+1,s+n+1);
for(i=c+1;i<=n;i++)
S+=s[i];
if(S>sol)sol=S;
return;
}
if(r1<r)
{
v[k]=0;
backL(k+1,r1+1);
v[k]=1;
backL(k+1,r1);
}
else
{
v[k]=1;
backL(k+1,r1);
}
}
void backC(int k, int c1)
{
int i,j,s[nmax],S;
if(k>n+1)return;
if(c1>c)return;
if(c1==c&&k==n+1)
{
S=0;
for(i=1;i<=m;i++)s[i]=0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
s[i]+=a[i][j]*v[j];
sort(s+1,s+m+1);
for(i=r+1;i<=m;i++)
S+=s[i];
if(S>sol)sol=S;
return;
}
if(c1<c)
{
v[k]=0;
backL(k+1,c1+1);
v[k]=1;
backL(k+1,c1);
}
else
{
v[k]=1;
backL(k+1,c1);
}
}