Cod sursa(job #3319416)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 1 noiembrie 2025 11:56:03
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <bits/stdc++.h>
using namespace std;

/*
    F  F     F
 1  1 -1  1  1 -> 1
 1  1 -1  1  1 -> 1
-1 -1 30 -1 -1 -> -30 F
 1  1 -1  1  1 -> 1
 1  1 -1  1  1 -> 1
                -----
                  34
*/

/*
2^nr_col <= 2^16 = 65536
*/

/* Plan de atac:
Luam totate variantele de flip pe coloane
Pentru o varianta de flip pe coloane determinam unde dam flip pe linii
Dintre toate astea luam maximul
*/

const int NMAX=20;

int N, M;
int mat[NMAX][NMAX];
int flip[NMAX];
int maxx=0;

void bkt(int k)
{
	if(k==M+1)
	{
		int suma_totala=0;
		for(int i=1;i<=N;++i)
		{
			int sum=0;
			for(int j=1;j<=M;++j)
			{
				if(flip[j]==1)
					sum=sum-mat[i][j];
				else
					sum=sum+mat[i][j];
			}

			if(sum>0)
				suma_totala+=sum;
			else
				suma_totala-=sum;
		}
		if(maxx<suma_totala)
			maxx=suma_totala;
	}
	else
	{
		for(flip[k]=0;flip[k]<2;++flip[k])
			bkt(k+1);
	}
}

int main()
{
	ifstream cin("flip.in");
	ofstream cout("flip.out");

	cin>>N>>M;
	for(int i=1;i<=N;++i)
		for(int j=1;j<=M;++j)
			cin>>mat[i][j];

	/*
	for(flip[1]=0;flip[1]<2;++flip[1])
		for(flip[2]=0;flip[2]<2;++flip[2])
			for(flip[3]=0;flip[3]<2;++flip[3])
				...
				{
					// Pas 2
				}
	*/
	bkt(1);

	cout<<maxx<<'\n';

	return 0;
}