Pagini recente » Cod sursa (job #1083301) | Cod sursa (job #669755) | Cod sursa (job #2648059) | Cod sursa (job #2146530) | Cod sursa (job #306351)
Cod sursa(job #306351)
#include <algorithm>
#define MAX 8005
#define MIN 25
using namespace std;
int a[MIN][MAX],x[MAX],y[MIN],s[MIN],sl[MIN],sc[MAX];
int n,m,r,c,sol,sum,sm;
void read ()
{
int i,j;
scanf ("%d%d%d%d",&m,&n,&r,&c);
if (m<n)
for (i=1; i<=m; ++i)
for (j=1; j<=n; ++j)
{
scanf ("%d",&a[i][j]);
sum+=a[i][j];
sl[i]+=a[i][j];
sc[j]+=a[i][j];
}
else
{
for (i=1; i<=m; ++i)
for (j=1; j<=n; ++j)
{
scanf ("%d",&a[n-j+1][i]);
sum+=a[n-j+1][i];
sl[n-j+1]+=a[n-j+1][i];
sc[i]+=a[n-j+1][i];
}
m^=n^=m^=n;
r^=c^=r^=c;
}
}
void check ()
{
int i,j;
for (i=1; i<=n; ++i)
{
x[i]=sc[i];
for (j=1; j<=m; ++j)
if (y[j])
x[i]-=a[j][i];
}
sort (x+1,x+n+1);
sm=sum;
for (i=1; i<=c; ++i)
sm-=x[i];
if (sm>sol)
sol=sm;
}
void back (int k)
{
int i;
if (k==r+1)
check ();
else
for (i=s[k-1]+1; i<=m; ++i)
if (!y[i])
{
s[k]=i;
y[i]=1;
sum-=sl[i];
back(k+1);
y[i]=1;
sum+=sl[i];
}
}
int main ()
{
freopen ("elimin.in","r",stdin);
freopen ("elimin.out","w",stdout);
read ();
back (1);
printf ("%d",sol);
return 0;
}