Cod sursa(job #2443603)

Utilizator EdyOnuEdy Onu EdyOnu Data 28 iulie 2019 18:27:59
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul II Marime 1.43 kb
// flip.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

//#include "pch.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <cmath>
using namespace std;


class Solver {

public:

	explicit Solver(istream&& in){
		__readData(move(in));
		__generateSequences(0);
	}
	

	int getMaxSum() const {
		return sumMax;
	}
	

private:

	void __readData(istream&& in) {

		in >> N >> M;

		for (int i = 0; i < N; ++i) {
			vector<int> line;
			for (int j = 0, value; j < M; ++j) {
				in >> value;
				line.push_back(value);
			}
			matrix.push_back(line);
		}

		stack.resize(N);
	}

	void __generateSequences(int level) {
			
		if (level == N) {
			sumMax = max<int>(
				sumMax,
				__getSumOnConfig()
			);
			return;
		}

		for (int i = -1; i <= 1; i += 2) {
			stack[level] = i;
			__generateSequences(level + 1);
		}
	}

	int __getSumOnConfig() const {

		int sum = 0;

		for (int col = 0; col < M; ++col) {
			int colSum = 0;
			for (int line = 0; line < N; ++line) {
				colSum += stack[line] * matrix[line][col];
			}
			sum += (colSum < 0) ? -colSum : colSum;
		}

		return sum;
	}
	


	int N, M, sumMax = numeric_limits<int>::min();
	vector<vector<int>> matrix;
	vector<int> stack;
};



int main() {
	ofstream{ "flip.out" } << Solver{ ifstream{ "flip.in" } }.getMaxSum();
}