Cod sursa(job #491246)

Utilizator Balmus_MaximBalmus Maximilian Balmus_Maxim Data 10 octombrie 2010 19:44:42
Problema Elimin Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <stdio.h>
#include <algorithm>
#define maxn 800

using namespace std;

int m,n,r,c,i,j,a[800][800],st[800],mm=0,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;
		return;
	}else{
		for(i=pi+1;i<=m-r+p;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",&m);
	scanf("%d",&n);
	scanf("%d",&r);
	scanf("%d",&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<=n;i++){
			for(j=1;j<=m;j++){
				scanf("%d",&a[i][j]);
			}
		}
		sch=m;m=n;n=sch;
		sch=r;r=c;c=sch;
	}
	for(i=1;i<=m;i++){
		con[i]=1;
	}
	back(0,0);
	printf("%d",mm);
	return 0;
}