Cod sursa(job #1267456)

Utilizator alexandru94hahahalera alexandru94 Data 19 noiembrie 2014 21:55:55
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb



#include <iostream>
#include <cstdlib>
#include <fstream>
#include <math.h>

using namespace std;

int main() {
	ifstream fin("flip.in");
	ofstream fout("flip.out");

	int N = 0, M = 0;
	fin>>N>>M;

	int m[N][M];

	for(int i = 0; i < N; i++) {
		for(int j = 0; j < M; j++) {
			fin>>m[i][j];
		}
	}

	int max = -1000002;

	if(N * log2(M) < M * log2(N)) {
	//e mai simplu sa generam pentru linii semne
		int range = pow(2, N);
		for(int k = 0; k < range; k++) {
			int subSumMax = 0;
			//facem suma pe coloane
			for(int j = 0; j < M; j++) {
				int sumcoli = 0;
				for(int i = 0; i < N; i++) {
					int semn = 1;
					if((k & (1 << i)) != 0) {
						semn = -1;
					}
					sumcoli += semn * m[i][j]; 
				}
				if(sumcoli < 0) {
					sumcoli = sumcoli * (-1);
				}
				subSumMax += sumcoli;
			}
			if(subSumMax > max) {
				max = subSumMax;
			}
		}
	} else {
		//e mai simplu sa generam pentru coloane semne
		int range = pow(2, M);
		for(int k = 0; k < range; k++) {
			int subSumMax = 0;
			//facem suma pe coloane
			
			for(int i = 0; i < N; i++) {
				int sumlini = 0;
				for(int j = 0; j < M; j++) {
					int semn = 1;
					if(k & (1 << j)) {
						semn = -1;
					}
					sumlini += semn * m[i][j]; 
				}
				if(sumlini < 0) {
					sumlini *= -1;
				}
				subSumMax += sumlini;
			}
			if(subSumMax > max) {
				max = subSumMax;
			}
		}
	}
	fout<<max;

	fin.close();
	fout.close();
}