Pagini recente » Cod sursa (job #1541164) | Cod sursa (job #163838) | Clasament cner12a | Cod sursa (job #3186940) | Cod sursa (job #8253)
Cod sursa(job #8253)
#include <stdio.h>
#include <stdlib.h>
#define infile "elimin.in"
#define outfile "elimin.out"
FILE *fin,*fout;
int m,n,r,c;
short int x[15][7300];
int sumamax=-1;
short int st[20],marcaj[20];
int suma[7300];
int pos(int li, int ls)
{
int i=0,j=-1,aux;
while(li<ls)
{
if(suma[li]>suma[ls])
{
aux=i; i=-j; j=-aux;
aux=suma[li]; suma[li]=suma[ls]; suma[ls]=aux;
}
li+=i;
ls+=j;
}
return li;
}
void quicksort(int li, int ls)
{
if(li<ls)
{int k=pos(li,ls);
quicksort(li,k-1);
quicksort(k+1,ls);}
}
void analize()
{
int i,j,rez=0;
for(i=0;i<m;i++)
marcaj[i]=0;
for(i=0;i<r;i++)
marcaj[st[i]]=1;
for(i=0;i<n;i++)
suma[i]=0;
for(i=0;i<m;i++)
if(!marcaj[i])
for(j=0;j<n;j++)
suma[j]+=x[i][j];
quicksort(0,n-1);
for(i=c;i<n;i++)
rez+=suma[i];
if(rez>sumamax)
sumamax=rez;
}
void back(short int k)
{
if(k==r)
{
analize();
return;
}
short int start=0,ls=m-r+k+1;
if(k>0)
start=st[k-1]+1;
for(st[k]=start;st[k]<ls;st[k]++)
back(k+1);
}
int main()
{
int i,j,aux,invers=0;
fin=fopen(infile,"r");
fscanf(fin,"%d %d %d %d",&m,&n,&r,&c);
if(m>15)
{
aux=m; m=n; n=aux;
aux=r; r=c; c=aux;
invers=1;
}
if(!invers)
for(i=0;i<m;i++)
for(j=0;j<n;j++)
fscanf(fin,"%d",&x[i][j]);
else
for(i=0;i<n;i++)
for(j=0;j<m;j++)
fscanf(fin,"%d",&x[j][i]);
fclose(fin);
back(0);
fout=fopen(outfile,"w");
fprintf(fout,"%d\n",sumamax);
fclose(fout);
return 0;
}