Cod sursa(job #2453713)

Utilizator 1chiriacOctavian Neculau 1chiriac Data 5 septembrie 2019 14:02:51
Problema Jocul Flip Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>

using namespace std;
ifstream fin ("flip.in");
ofstream fout ("flip.out");
int n,v[20],sumalin[20],suma,maxim=-10000000,m,a[20][20],sumacrt;
int succesor (int k)
{
	if(v[k]<1 && k<=n)
	{
		v[k]++;
		return 1;
	}
	return 0;
}
void solutie (int n)
{
	suma=0;
	for(int i=1;i<=n;i++)
		if(v[i]==0)
			suma+=sumalin[i];
		else if(v[i]==1)
			suma-=sumalin[i];
	for(int i=1;i<=m;i++)
	{
		sumacrt=0;
		for(int ii=1;ii<=n;ii++)
			if(v[ii]==0)
				sumacrt+=a[ii][i];
			else
				sumacrt-=a[ii][i];
		if(sumacrt<sumacrt*(-1))
			suma=suma-sumacrt-sumacrt;
	}
	if(suma>maxim)
		maxim=suma;
}
void backt ()
{
	int i,k;
	k=1;v[k]=-1;
	while(k>0)
	{
		i=0;
		while(succesor(k)==1 && i==0)
			i=1;
		solutie(n);
		if(i==0)
			k--;
		else
			k++,v[k]=-1;
	}
}
int main ()
{
	fin>>n>>m;
	for(int ij=1;ij<=n;ij++)
	{
		sumacrt=0;
		for(int j=1;j<=m;j++)
		{
			fin>>a[ij][j];
			sumacrt+=a[ij][j];
		}
		sumalin[ij]=sumacrt;
	}
	backt();
	fout<<maxim;
	return 0;
}