Cod sursa(job #9109)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 26 ianuarie 2007 19:40:37
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define maxn 1010
#define maxx 110

short a[maxn][maxx];
int n,m,r,c,sol;
int sum[maxn];

int count(int x)
{
    int i,rez=0;
    
    for (i=0;i<m;i++) 
      if ((x&(1<<i))!=0) rez++;
      
    return rez;
}

int main()
{
    freopen("elimin.in","r",stdin);
    freopen("elimin.out","w",stdout);
    
    scanf("%d %d %d %d",&n,&m,&r,&c);
    
    int i,j,k,aux;
    
    if (m>n)
    {
       for (i=1;i<=n;i++)
         for (j=1;j<=m;j++) scanf("%d",&a[j][i]);
         
       aux=m;
       m=n;
       n=aux;
       aux=r;
       r=c;
       c=aux;
    }
    else for (i=1;i<=n;i++)      
           for (j=1;j<=m;j++) scanf("%d",&a[i][j]);     
                     
    for (i=0;i<1<<m;i++) 
      if (count(i)==c)
      {
            for (j=1;j<=n;j++)
            {
               sum[j]=0;
                
               for (k=1;k<=m;k++) 
                 if ((i&(1<<(k-1)))==0) sum[j]+=a[j][k];
            }
                              
            sort(sum+1,sum+n+1);
                             
            for (j=n-1;j>r;j--) sum[n]+=sum[j];
            if (sum[n]>sol) sol=sum[n];
      }
        
    printf("%d\n",sol);
        
    return 0;
}