Pagini recente » Cod sursa (job #1642641) | Cod sursa (job #1085333) | Cod sursa (job #1045854) | Cod sursa (job #2472129) | Cod sursa (job #2443643)
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
ifstream f("flip.in");
ofstream g("flip.out");
int n, m, a[17][17], maxS = -999999999, v[2] = {-1, 1};
void citire(int &n, int &m, int a[][17]) {
f >> n >> m;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
f >> a[i][j];
///fiecare linie are la sfarsit cate un element care memoreaza daca linia e flipped sau nu
for(int i = 0; i < n; i++)
a[i][m] = 1;
}
///suma pe o coloana
int sum(int c) {
int s = 0;
for(int i = 0; i < n; i++)
s +=a[i][c];
return s;
}
///flip la linie
void flip(int l) {
for(int i = 0; i <= m; i++)
a[l][i] *= -1;
}
int Msum(int a[][17]) {
int s = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
s+= a[i][j];
return s;
}
///backtracking pt linii si pt a obtine suma maxima
///adunam abs de fiecare coloana
void backtracking(int k) {
for(int i = 0; i <= 1; i++) {
if(a[k][m] != v[i]) {
flip(k);
//cout << "flip " << k << '\n';
int currentS = 0;
for(int j = 0; j < m; j++)
currentS+= abs(sum(j));
if(currentS > maxS) {
maxS = currentS;
//cout << maxS <<'\n';
}
}
if(k < n-1)
backtracking(k+1);
}
}
int main() {
citire(n, m, a);
maxS = Msum(a);
backtracking(0);
g << maxS;
}