Cod sursa(job #1873385)

Utilizator ButmalaiDanButmalai Dan ButmalaiDan Data 8 februarie 2017 23:36:45
Problema Jocul Flip Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include<bits/stdc++.h>
using namespace std;

int n, m, a[20][20], b[20], rez[20], sum_rez = -1<<30,auxa[20][20],sum_rez1 = -1<<30;
int main()
{
	ifstream cin("flip.in");
	ofstream cout("flip.out");
	cin >> n >> m;
	for (int i = 0 ; i < n; i++) for (int j = 0 ; j < m; j++) {cin >> a[i][j];auxa[i][j] = a[i][j];}
	for (int i = 0; i < 1<<m; i++)
	{
		int aux = i;
		int sum = 0;
		for(int j = 0; j < m; j++) b[j] = aux%2, aux/=2;
		for(int j = 0; j < m; j++) 
			for(int z = 0; z < n; z++)
			{
				if(b[j]) sum -= a[z][j];
				else sum += a[z][j];
			}
		if (sum > sum_rez)
		{
			sum_rez = sum;
			for(int j = 0; j < m; j++) rez[j] = b[j];
		}
	}
	for (int i = 0; i < m; i++)
	{
		if(rez[i]){
			for (int j = 0; j < n; j++)
			{
				auxa[j][i] *= -1;
			}
		}
	}
	for (int i = 0 ; i < n; i++)
	{
		int aux_sum = 0;
		for(int j = 0; j < m; j++)
		{
			aux_sum += a[i][j];
		}
		if(aux_sum < 0) sum_rez += -2*aux_sum;
	}
	
	//
	for (int i = 0 ; i < n; i++) for (int j = 0 ; j < m; j++) {auxa[i][j] = a[i][j];}
	for (int i = 0; i < 1<<n; i++)
	{
		int aux = i;
		int sum = 0;
		for(int j = 0; j < n; j++) b[j] = aux%2, aux/=2;
		for(int j = 0; j < n; j++) 
			for(int z = 0; z <m; z++)
			{
				if(b[j]) sum -= a[z][j];
				else sum += a[z][j];
			}
		if (sum > sum_rez1)
		{
			sum_rez1 = sum;
			for(int j = 0; j < n; j++) rez[j] = b[j];
		}
	}
	for (int i = 0; i < n; i++)
	{
		if(rez[i]){
			for (int j = 0; j < m; j++)
			{
				auxa[j][i] *= -1;
			}
		}
	}
	for (int i = 0 ; i < m; i++)
	{
		int aux_sum = 0;
		for(int j = 0; j < n; j++)
		{
			aux_sum += a[i][j];
		}
		if(aux_sum < 0) sum_rez1 += -2*aux_sum;
	}
	//
	cout << max(sum_rez,sum_rez1);
}