Cod sursa(job #130314)

Utilizator Snavenportnespecificat Snavenport Data 31 ianuarie 2008 20:07:52
Problema Elimin Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <fstream.h>

int sol[200],n,m,r,c;  // n-nr de coloane, m-nr de linii
int a[200][200],b[200][200];
long Smax=0;

void matcpy()
{
     int i,j;
     for (i=1;i<=m;i++)
        for (j=1;j<=n;j++)
           b[i][j]=a[i][j];
}

void sterglinie()
{

     int i,j;
     for (i=1;i<=m;i++)
        for (j=1;j<=n;j++)
          if (sol[i]==1)
              b[i][j]=0;
}                                   

long minime[200];

void calcul()
{
     int i,j;
     for (i=1;i<=n;i++)
        {
        long s=0;               
        for (j=1;j<=m;j++) 
            s=s+b[j][i];
        minime[i]=s;
        }
}

void sort()
{
     int i,j;
     long aux;
     for (i=1;i<=n-1;i++)       
       for (j=i+1;j<=n;j++)
         if (minime[i]>minime[j])
           {
                   aux=minime[i];
                   minime[i]=minime[j];
                   minime[j]=aux;
           }
}

void rezolva()
{
     matcpy();
     sterglinie();
     calcul();
     sort();
     long S=0;
     for (int i=c+1;i<=n;i++)
        S=S+minime[i];
     if (S>Smax)
        Smax=S;
}   

void back(int k)
{
    int i,j,nr;
    for (i=0;i<=1;i++)
       {
           sol[k]=i;
           nr=0;
           for (j=1;j<=k;j++)
             if (sol[j]==1)
                nr++;
          if (k==m)
         {  if (nr==r)
                 rezolva();
                 }
          else
             back(k+1);
       }
}

ifstream f("elimin.in");
ofstream g("elimin.out");
      
main()
{
     f>>m>>n>>r>>c;
     for (int i=1;i<=m;i++)
       for (int j=1;j<=n;j++)
         f>>a[i][j];
     back(1);    
     g<<Smax;
}