Cod sursa(job #711615)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 12 martie 2012 14:43:13
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <cstdio>
#include <iostream>
#include <algorithm>
#define LE 4000
#define FOR for(i=1;i<=n;++i) for(j=1;j<=m;++j)
using namespace std;
int i,j,m,n,MAX=-1000000,S[LE],SE[LE],semn[LE],nrl,nrc;

short int a[LE][LE],M[LE][LE];
int suma(){
	int rez=0;
	for(i=1;i<=m;++i) S[i]=0;
	
	FOR{
		M[i][j]=a[i][j];M[i][j]*=semn[i];
		S[j]+=M[i][j];
	}
	
	sort(S+1,S+m+1);
	for(i=nrc+1;i<=m;++i) rez+=S[i];
	MAX=max(rez,MAX);
}
	
int back(int k,int p){
    if(k==n+1&&p==nrl) suma();
	
	if (k<=n) {
	   semn[k]=1,back(k+1,p);
	   if (p<=nrl) semn[k]=0,back(k+1,p+1);
    }
}
int main()
{
	freopen("elimin.in","r",stdin);
	freopen("elimin.out","w",stdout);
	
	scanf("%ld%ld%ld%ld",&n,&m,&nrl,&nrc);
	FOR if(n<=m) scanf("%ld",&a[i][j]); else  scanf("%ld",&a[j][i]);
	
	if (n>m) swap(n,m),swap(nrl,nrc);

	back(1,0);
	printf("%ld\n",MAX);
	return 0;
}