Pagini recente » Cod sursa (job #1310927) | Cod sursa (job #2149027) | Cod sursa (job #2296171) | Cod sursa (job #2740067) | Cod sursa (job #43474)
Cod sursa(job #43474)
#include <stdio.h>
FILE *fin,*fout;
long smax=-10000000;
int m,n,r,c,l;
int min[550],mins[550],sum[550],viz[550],nr[550],a[550][550]; //550
void reheap(int i)
{ int st=i*2;
int dr=i*2+1;
int aux,max;
max=i;
if (st<=l&&min[st]<min[max])
max=st;
if (dr<=l&&min[dr]<min[max])
max=dr;
if (max!=i)
{ aux=min[i];
min[i]=min[max];
min[max]=aux;
reheap(max);
}
}
void hsort()
{
l=n;
int i,aux;
for (i=n/2;i>=1;i--)
reheap(i);
for (i=n;i>=n-m+1;i--)
{ aux=min[i];
min[i]=min[1];
min[1]=aux;
l--;
reheap(1);
}
}
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];
}
hsort();
for (j=li-1;j>li-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;
}