Cod sursa(job #41812)

Utilizator andrei_infoMirestean Andrei andrei_info Data 28 martie 2007 16:36:22
Problema Elimin Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int a[15][550], suma[550],x[15],n,m,r,c,s,rez;

void citire();
void back(int k);

int main()
{
citire();
back(1);
freopen("elimin.out","w",stdout);
printf("%d",rez);
fclose(stdout);
return 0;
}

void citire()
{
int i,j,aux;
freopen("elimin.in","r",stdin);
scanf("%d %d %d %d", &m,&n,&r,&c);
if (m <=15)
   for (i=1; i<=m; i++)
       for (j=1; j<=n; j++)
           scanf("%d",&a[i][j]);
else
    {
    aux=r; r=c; c=aux;
    for (j=1; j<=m; j++)
        for (i=1; i<=n; i++)
            scanf("%d", &a[i][j]);
    aux=m; m=n; n=aux;
    }
fclose(stdin);
}

int comp(const void *a, const void *b)
{
    if( (*(int *)a) >  (*(int*)b)) return 1;
    return -1;
}

void calc()
{
int i,j,rr;
memset(suma,0,sizeof(suma));
for (i=1; i<=m; i++)
    if (x[i] ==1)
       for (j=1; j<=n; j++)
           suma[j]+=a[i][j];
qsort(suma,n+1,sizeof(int),comp);
rr=0;
for (i=n; i>=c+1; i--)
    rr+=suma[i];
if (rr > rez) rez=rr;
}

void back(int k)
{
int i;
if (k == m+1)
   {
   if (s==r) calc();
   }
else
    for (i=0; i<=1; i++)
        {
        x[k]=i;
        if (i == 0) s+=1;
        if (s<=r )
           back(k+1);
        if (i ==0) s-=1;
        }
}