Pagini recente » Cod sursa (job #1561484) | Cod sursa (job #1609710) | Cod sursa (job #2752784) | Cod sursa (job #175680) | Cod sursa (job #43440)
Cod sursa(job #43440)
#include <stdio.h>
FILE *fin,*fout;
long smax=-10000000;
int m,n,r,c;
int min[700],mins[700],sum[700],viz[700],nr[700],a[70][70]; //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,nr=0;
long sp=0;
for (j=0;j<li;j++)
{
min[nr++]=sum[j];
sp+=sum[j];
}
sort(0,nr-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;
}
for (i=nr[k-1]+1;i<=(m-c+k);i++)
{
if (viz[i]!=1)
{if (k==0&&i==(m-c+1)) return;
viz[i]=1;
nr[k]=i;
for (j=0;j<n;j++) sum[j]-=a[j][i];
back (k+1);
for (j=0;j<n;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;
}
for (i=nr[k-1]+1;i<=(n-r+k);i++)
{
if (viz[i]!=1)
{if (k==0&&i==(m-r+1)) return;
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;
}