Pagini recente » Cod sursa (job #2984498) | Cod sursa (job #2893150) | Cod sursa (job #194833) | Cod sursa (job #2076759) | Cod sursa (job #43464)
Cod sursa(job #43464)
#include <stdio.h>
FILE *fin,*fout;
long smax=-10000000;
int m,n,r,c;
int min[550],mins[550],sum[550],viz[550],nr[550],a[550][550]; //550
void sort(int l, int r)
{
int m = (l + r) >> 1, i, j, k;
if (l == r) return;
sort(l, m);
sort(m + 1, r);
for (i=l, j=m+1, k=l; i<=m || j<=r; )
if (j > r || (i <= m && min[i] < min[j]))
mins[k++] = min[i++];
else
mins[k++] = min[j++];
for (k = l; k <= r; k++) min[k] = mins[k];
}
int suma(int lim,int li)
{int j,nr2=0;
long sp=0;
for (j=0;j<li;j++)
{
min[nr2++]=sum[j];
sp+=sum[j];
}
sort(0,nr2-1);
for (j=0;j<lim;j++) sp-=min[j];
return sp;
}
void back (int k)
{int i,j;
long s;
if (k==c)
{
s=suma(r,m);
if (smax<s) smax=s;
return;
}
if (k==0) nr[k-1]=-1;
for (i=nr[k-1]+1;i<=(n-c+k);i++)
{
if (viz[i]!=1)
{
viz[i]=1;
nr[k]=i;
for (j=0;j<m;j++) sum[j]-=a[j][i];
back (k+1);
for (j=0;j<m;j++) sum[j]+=a[j][i];
viz[i]=0;
}
}
}
void back2(int k)
{int i,j;
long s;
if (k==r)
{
s=suma(c,n);
if (smax<s) smax=s;
return;
}
if (k==0) nr[k-1]=-1;
for (i=nr[k-1]+1;i<=(m-r+k);i++)
{
if (viz[i]!=1)
{
viz[i]=1;
nr[k]=i;
for (j=0;j<n;j++) sum[j]-=a[i][j];
back2 (k+1);
for (j=0;j<n;j++) sum[j]+=a[i][j];
viz[i]=0;
}
}
}
int main()
{int i,j;
fin=fopen("elimin.in","rt");
fout=fopen("elimin.out","wt");
fscanf(fin,"%d %d %d %d\n",&m,&n,&r,&c);
if (n<=m){
for (i=0;i<m;i++)
for (j=0;j<n;j++)
{
fscanf(fin,"%d",&a[i][j]);
sum[i]+=a[i][j];
}
back(0);
}
else {
for (i=0;i<m;i++)
for (j=0;j<n;j++)
{
fscanf(fin,"%d",&a[i][j]);
sum[j]+=a[i][j];
}
back2(0);
}
fprintf(fout,"%ld\n",smax);
fcloseall();
return 0;
}