Cod sursa(job #714470)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 15 martie 2012 19:28:30
Problema Elimin Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
int a[16][1001],st[16],n,l,m,r,c,maxim,d[16][1001],v[1001];
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]=0;
	s=0;
	for(i=1;i<=ll;i++) 
		for(j=1;j<=m;j++) {
			s=s+d[i][j];
			v[j]=v[j]+d[i][j];
		}
	sort(v+1,v+m+1);
	for(i=1;i<=c;i++)
		s=s-v[i];
	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==5)
		while(1);
	if(n<=15)
		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;
}