Cod sursa(job #575346)

Utilizator Anamaria20Cotirlea Anamaria Anamaria20 Data 8 aprilie 2011 10:33:14
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <stdio.h> 
#include <algorithm> 
 
using namespace std; 
  
int m,n,r,c,i,j,a[800][800],st[800],mm,sch,con[20]; 
  
void back(int p,int pi) 
{ 
    int i,j;
	
    if(p==r)     
	{ 
		int suma=0; 
	
		for(i=1;i<=n;i++) st[i]=0; 
		
		for(i=1;i<=m;i++) 
			for(j=1;j<=n;j++) 
				st[j]+=a[i][j]*con[i]; 
        
		sort(st+1,st+n+1); 
        
		for(i=n;i>c;i--)
			suma+=st[i]; 
        
		if(suma>mm) mm=suma; 
    }
	else
	{ 
		for(i=pi+1;i<=m-r+p+1;i++)
		{ 
			con[i]=0; 
			back(p+1,i); 
			con[i]=1; 
        } 
	} 
} 
             
int main() 
{ 
    freopen("elimin.in","r",stdin); 
	freopen("elimin.out","w",stdout); 
    
	scanf("%d %d %d %d",&m,&n,&r,&c); 
    
	if(m<=n)
	{ 
		for(i=1;i<=m;i++)
			for(j=1;j<=n;j++) 
				scanf("%d",&a[i][j]); 
	} 
    else
	{ 
		for(i=1;i<=m;i++)
			for(j=1;j<=n;j++)
				scanf("%d",&a[j][i]); 
			
		sch=m;m=n;n=sch; 
		sch=r;r=c;c=sch; 
    }
     
	for(i=1;i<=20;i++)
        con[i]=1; 
    
	back(0,0); 
    
	printf("%d",mm); 
    
	return 0; 
}