Cod sursa(job #250717)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 31 ianuarie 2009 17:13:44
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <cstdio>
#include <algorithm>
using namespace std;

long v[20][8000], s[8000], a[20], n, m, r, c, mx;

void verif()
{
    long i, b[8000];
    for (i=1; i<=m; i++) b[i]=s[i];
	sort(b+1,b+m+1);
	long t;
	t=0;
	for (i=c+1; i<=m; t+=b[i++]);
	if (t>mx) mx=t;
}


void back(long p, long k)
{
    int i;
	if (k==r) verif();
	if ((p<=n)&(k<r))
	{
		back(p+1,k);
		a[p]=1;
		for (i=1; i<=m; i++) s[i]-=v[p][i];
		back(p+1,k+1);
		for (i=1; i<=m; i++) s[i]+=v[p][i];
        a[p]=0;
    }
}

int main()
{
	freopen("elimin.in","r",stdin);
	freopen("elimin.out","w",stdout);
	scanf("%ld %ld %ld %ld",&n,&m,&r,&c);
	int i,j;
	if (n>m)
	{
		long x=n;
		n=m;
		m=x;
		x=r;
		r=c;
		c=x;
		for (i=1; i<=m; i++)
		    for (j=1; j<=n; j++) scanf("%ld",&v[j][i]);
	} else
	    for (i=1; i<=n; i++)
    	    for (j=1; j<=m; j++) scanf("%ld",&v[i][j]);
    for (i=1; i<=m; i++)
		for (j=1; j<=n; s[i]+=v[j++][i]);
	back(1,0);
	printf("%ld",mx);
	fclose(stdin);
	fclose(stdout);
}