Cod sursa(job #714427)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 15 martie 2012 19:05:39
Problema Elimin Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
struct coloane {
	int poz,val;
};
int a[50][3001],st[50],n,l,m,r,c,maxim,d[50][3001],col[3001];
coloane v[3001];
inline bool cmp(const coloane a, const coloane b)
{
	return a.val<=b.val;
}
void verifica()
{
	int i,j,nr,ll,s;
	nr=1;
	ll=0;
	for(i=1;i<=n;i++) 
		if(st[nr]!=i) {
			ll++;
			for(j=1;j<=m;j++)
				d[ll][j]=a[i][j];
		}
		else nr++;
	for(j=1;j<=m;j++) {
		v[j].val=0;
		v[j].poz=j;
	}
	for(i=1;i<=ll;i++)
		for(j=1;j<=m;j++)
			v[j].val=v[j].val+d[i][j];
	sort(v+1,v+m+1,cmp);
	for(i=1;i<=c;i++)
		col[i]=v[i].poz;
	sort(col+1,col+c+1);
	nr=1;
	s=0;
	for(i=1;i<=m;i++)
		if(col[nr]!=i) 
			for(j=1;j<=ll;j++)
				s=s+d[j][i];
		else nr++;
	if(s>maxim)
		maxim=s;
}
inline void bktr(int p)
{
	int pval;
	for(pval=st[p-1]+1;pval<=n-r+p;pval++) {
		st[p]=pval;
		if(p==r)
			verifica();
		else bktr(p+1);
	}
}
int main ()
{
	int i,j,aux;
	ifstream f("elimin.in");
	ofstream g("elimin.out");
	f>>n>>m>>r>>c;
	if(n<=4)
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
				f>>a[i][j];
	else {
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
				f>>a[j][i];
		aux=n;
		n=m;
		m=aux;
		aux=r;
		r=c;
		c=aux;
	}
	f.close();
	maxim=-2000000000;
	bktr(1);
	g<<maxim;
	g.close();
	return 0;
}