Pagini recente » Cod sursa (job #1338168) | Cod sursa (job #811317) | Cod sursa (job #2168853) | Cod sursa (job #1958659) | Cod sursa (job #15086)
Cod sursa(job #15086)
#include <stdio.h>
#define NMAX 8192
#define INF "elimin.in"
#define OUF "elimin.out"
long int a[NMAX][16],bit[16]={0},v[NMAX],n,m,r,c,total;
void qsort(int p,int q)
{
int i,j,piv,aux;
i=p;j=q;piv=v[i];
do{
while(v[i]<piv) i++;
while(v[j]>piv) j--;
if(i<=j)
{
aux=v[i];v[i]=v[j];v[j]=aux;
i++;j--;
}
}while(i<j);
if(i<q) qsort(i,q);
if(j>p) qsort(p,j);
}
void gensol()
{
register int i,j,sum;
for(i=1;i<=n;i++)
{
sum=0;
for(j=1;j<=m;j++)
if(!bit[j]) sum+=a[i][j];
v[i]=sum;
}
qsort(1,n);
sum=0;
for(i=r+1;i<=n;i++) sum+=v[i];
// printf("%d ",sum);
if(sum>total) total=sum;
}
void back(int k)
{
int i;
for(i=k;i<=m;i++)
{
if(!bit[i])
{
bit[i]=1;
if(k==c) gensol();
else back(k+1);
bit[i]=0;
}
}
}
int main()
{
int i,j,aux;
FILE *in,*out;
in=fopen(INF,"r");
out=fopen(OUF,"w");
fscanf(in,"%d %d %d %d",&n,&m,&r,&c);
if(m<16)
{
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
fscanf(in,"%d",&a[i][j]);
}
else
{
for(i=1;i<=n;i++)
for(j=1;j<=m;j++) fscanf(in,"%d",&a[j][i]);
aux=n;n=m;m=aux;
aux=r;r=c;c=aux;
}
/*printf("%d %d\n\n",r,c);
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++) printf("%d ",a[i][j]);
printf("\n");
}*/
total=0;
back(1);
if(c<1) gensol();
fprintf(out,"%d",total);
fclose(in);fclose(out);
return 0;
}