Cod sursa(job #53007)

Utilizator floringh06Florin Ghesu floringh06 Data 20 aprilie 2007 16:53:23
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
using namespace std;
#include<fstream>
#include<stdio.h>

int a[550][17],sl[550],sc[17];
int m,n,r,c;

int nr1(int x,int col)
 {
 int i,j=0;
 for(i=1;i<(1<<n);i<<=1)
    if(i&x)
      j++;
      
 if(j==col)
   return 1;
 return 0;           
 }
 
int main()
{
FILE *fin=fopen("elimin.in","r"),
     *fout=fopen("elimin.out","w");
     
fscanf(fin,"%d%d%d%d",&m,&n,&r,&c);
int i,j,inv=0,k,totl[550];
if(m<n)
  {
  inv=1;
  m^=n;
  n^=m;
  m^=n;
  
  r^=c;
  c^=r;
  r^=c;
  
  for(j=1;j<=n;j++)
    for(i=1;i<=m;i++)
       fscanf(fin,"%d",&a[i][j]);     
  }
else
  {
  for(i=1;i<=m;i++)
    for(j=1;j<=n;j++)
      fscanf(fin,"%d",&a[i][j]);     
  }
  
int sol=-1,crt,tot=0;
int x=0;

memset(totl,0,sizeof totl);
memset(sc,0,sizeof sc);
for(i=1;i<=m;i++)
 for(j=1;j<=n;j++)
   {
   tot+=a[i][j];
   sc[j]+=a[i][j];   
   totl[i]+=a[i][j];
   }

for(x=0;x<(1<<n);x++)
   if(nr1(x,c))
     {
     crt=tot;
     
     for(i=0;i<n;i++)
        if(x&(1<<i))
           crt-=sc[i+1];

     for(i=1;i<=m;i++)
        sl[i]=totl[i];      

     for(j=1;j<=n;j++)
       if((1<<(j-1))&x)         
         for(i=1;i<=m;i++)
           sl[i]-=a[i][j];
           
     for(i=1;i<=m;i++)
        {
        j=i;
        while(j/2&&sl[j/2]<sl[j])
            {
            sl[j/2]^=sl[j];
            sl[j]^=sl[j/2];
            sl[j/2]^=sl[j]; 
            j/=2;
            }              
        }
        
     i=m;
     while(i>1)
       {
       sl[i]^=sl[1];
       sl[1]^=sl[i];
       sl[i]^=sl[1]; 
       i--;
       
       j=1;
       while(1)
         {
         k=2*j;
         if(k>i) break;
         if(k+1<=i&&sl[k+1]>sl[k]) k++;
         if(sl[k]<sl[j]) break;
         
         sl[k]^=sl[j];
         sl[j]^=sl[k];
         sl[k]^=sl[j]; 
         j=k;
         }        
       }
       
     for(i=1;i<=r;i++)
        crt-=sl[i];
     
     if(crt>sol)
       sol=crt;
     }

fprintf(fout,"%d\n",sol);

fclose(fin);
fclose(fout);
return 0;
}