Cod sursa(job #8236)

Utilizator stef2nStefan Istrate stef2n Data 23 ianuarie 2007 22:58:04
Problema Elimin Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <stdio.h>
#include <stdlib.h>

#define infile "elimin.in"
#define outfile "elimin.out"
FILE *fin,*fout;
int m,n,r,c,x[15][7300];
int sumamax=-1;
int st[20],marcaj[20];
int suma[7300];

inline int cmp(const void *ma, const void *mb)
  {
   int a=*((int *)ma);
   int b=*((int *)mb);
   return -(a<b)+(a>b);
  }

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];
   qsort(suma,n,sizeof(int),cmp);
   for(i=c;i<n;i++)
      rez+=suma[i];
   if(rez>sumamax)
     sumamax=rez;
  }

void back(int k)
  {
   if(k==r)
     {
      analize();
      return;
     }
   int start=0;
   if(k>0)
     start=st[k-1]+1;
   for(st[k]=start;st[k]<m-r+k+1;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;
}