Cod sursa(job #597212)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 21 iunie 2011 14:16:27
Problema Elimin Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

inline void swap(short &a, short &b) {
	short tm=a;
	a=b;
	b=tm;
}

short n,m,r,c,x[800][800],smax=-10000,aa,sol[20];
int s[600];

int ver() {
	int i,j,ss[800],ssum=0;
	
	for(j=1;j<=n;++j)
		ss[j]=s[j];
	
	for(i=1;i<=m;++i) if(sol[i])
		for(j=1;j<=n;++j)
			ss[j]-=x[i][j];
	
	sort(&ss[1],&ss[n+1]);
		
	for(j=c+1;j<=n;++j)
		ssum+=ss[j];
	return ssum;
}

void back(int p) {
	int i;
	if(p==m+1 && aa==r) {
		i=ver();
		if(i>smax)
			smax=i;
		return;
	}
	if(p==m+1)
		return;
	for(i=0;i!=2;++i) {
		sol[p]=i;
		if(i) {
			++aa;
			if(aa>r) {
				--aa;
				return;
			}
		}
		back(p+1);
		if(i)
			--aa;
	}
}

int main() {
	int i,j,mm;
	freopen("elimin.in","r",stdin);
	freopen("elimin.out","w",stdout);
	scanf("%d%d%d%d",&mm,&n,&r,&c);
	
	m=mm;
	
	for(i=1;i<=m;++i)
		for(j=1;j<=n;++j)
			scanf("%d",&x[i][j]);
	if(m>n) {
		for(i=1;i<=m;++i)
			for(j=1;j<=n;++j)
				x[j][i]=x[i][j];
		swap(m,n);
		swap(r,c);
	}
	for(i=1;i<=m;++i)
		for(j=1;j<=n;++j)
			s[j]+=x[i][j];
		
	back(1);
	
	printf("%d",smax);
	return 0;
}