Cod sursa(job #8252)

Utilizator stef2nStefan Istrate stef2n Data 23 ianuarie 2007 23:19:21
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#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;
}