Cod sursa(job #330130)

Utilizator xaphariusMihai Suteu xapharius Data 8 iulie 2009 20:50:14
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<vector>
using namespace std;

int M, N, A[16][16], Max;
vector<int> st;

void citire(){
	scanf("%d%d", &N, &M);
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < M; ++j)
			scanf("%d", &A[i][j]);
}

void back(){
	
	if ((int)st.size() >= N){
		int sum = 0;
		for(int i = 0; i < M; ++i){
			int temp = 0;
			for (int j = 0; j < N; ++j) temp += A[j][i];
			sum += temp < 0? -temp: temp;
		}
		if (sum > Max) Max = sum;
	}
	else{
		st.push_back(-1);
		for (int i = 0; i < M; ++i)	A[(int)st.size()- 1][i] *= -1;
		back();
		st.push_back(1);
		for (int i = 0; i < M; ++i)	A[(int)st.size() - 1][i] *= -1;
		back();
	}
	if (st.size()) st.pop_back();
}

int main(){
	freopen("flip.in", "r", stdin);
	freopen("flip.out", "w", stdout);
	citire();
	back();
	printf("%d", Max);
}