Cod sursa(job #11328)

Utilizator devilkindSavin Tiberiu devilkind Data 31 ianuarie 2007 13:10:04
Problema Elimin Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <stdio.h>
#include <stdlib.h>
#define NMAX 2000

long int a[20][NMAX],n,m,i,j,k,r,c,st[20];
long int conf[20],sl[20],sc[NMAX],s,smax;

FILE *f = fopen("elimin.in","rt"), *g = fopen("elimin.out","wt");

void citire()
{
fscanf(f,"%ld %ld %ld %ld",&n,&m,&r,&c);

if (m<n) {
         for (i=1;i<=n;i++)
             for (j=1;j<=m;j++)
                 {fscanf(f,"%ld",&a[j][i]);
                 sl[j]+=a[j][i];
                 sc[i]+=a[j][i];
                 }
         k=n;
         n=m;
         m=k;
         k=r;
         r=c;
         c=k;
         return;
         }
 for (i=1;i<=n;i++)
             for (j=1;j<=m;j++)
                 {fscanf(f,"%ld",&a[i][j]);
                 sl[i]+=a[i][j];
                 sc[j]+=a[i][j];
                 }
}

int cmp(const void *x, const void*y)
{
return * (long int *) x - * (long int *) y;}

void verif()
{
long int s1[20],s2[NMAX];
for (i=1;i<=n;i++)
    s1[i]=sl[i];
for (i=1;i<=m;i++)
    s2[i]=sc[i];
    
for (i=1;i<=n;i++)
    if (st[i]==1)
       {s1[i]=0;
       for (j=1;j<=m;j++)
           s2[j]-=a[i][j];
       }
s2[0]=0;
qsort(s2, m+1, sizeof(long int),cmp);
s=0;
for (i=c+1;i<=m;i++)
    s+=s2[i];
if (s>smax) smax=s;
}



void back(long int nivel, long int nr)
{
if (nivel==n+1)
	{if (nr==r) verif();}
   else {
        st[nivel]=0;
        back(nivel+1,nr);
        if (nr<r)
           {st[nivel]=1;
           back(nivel+1,nr+1);
           }
        }

}



int main()
{
citire();
smax=0;
back(1,0);
fprintf(g,"%ld",smax);
fclose(f);
fclose(g);
return 0;
}