Cod sursa(job #253303)

Utilizator 630r63Ilinca George Mihai 630r63 Data 5 februarie 2009 17:31:14
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
 #include <stdio.h>  
 #include <stdlib.h>  
 #include <algorithm>  
 using namespace std;  
 int n,m,ln,cl;  
 int sum[600],nr[550][550],rezultat;  
 char sol[20];  
 void back(int poz,int val){  
     if(poz>m+1)  
         return;  
     if(val==cl){  
         int i,j;  
         for(i=1;i<=n;++i){  
             sum[i]=0;  
             for(j=1;j<=m;++j){  
                 if(!sol[j])  
                     sum[i]+=nr[i][j];  
             }  
         }  
         sort(sum+1,sum+n+1);  
         j=0;  
         for(i=ln+1;i<=n;++i)  
             j+=sum[i];  
         if (j>rezultat)  
           rezultat=j;  
     }  
     else{  
         sol[poz]=1;  
         back(poz+1,val+1);  
         sol[poz]=0;  
         back(poz+1,val);  
     }  
 }  
 int main(){  
     freopen("elimin.in","r",stdin);  
     freopen("elimin.out","w",stdout);  
     int i,j;  
     srand(time(NULL));  
     scanf("%d%d%d%d",&n,&m,&ln,&cl);  
     rezultat=-100000000;  
     if(m>15 || m>n){  
         i=n;n=m;m=i;  
         i=ln;ln=cl;cl=i;  
         for(j=1;j<=m;++j){  
             for(i=1;i<=n;++i)  
                 scanf("%d",&nr[i][j]);  
         }  
     }  
     else{  
         for(i=1;i<=n;++i){  
             for(j=1;j<=m;++j)  
                 scanf("%d",&nr[i][j]);  
         }  
     }  
     back(1,0);  
     printf("%d\n",rezultat);  
     fclose(stdin);  
     fclose(stdout);  
     exit(0);  
}