Pagini recente » Cod sursa (job #1917322) | Cod sursa (job #622432) | Cod sursa (job #3142900) | Cod sursa (job #2737288) | Cod sursa (job #1377799)
#include<fstream>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
long long getSum(int table[16][16], int N, int M) {
long long sum = 0;
for(int i = 0; i < N; ++i) {
for(int j = 0; j < M; ++j) {
sum += table[i][j];
}
}
return sum;
}
void flipCols(int table[16][16], int N, int M,
vector<int> lines, long long& actualSum) {
for(int i = 0; i < N; ++i) {
if(lines[i] == 1) {
for(int j = 0; j < M; ++j) {
table[i][j] = -table[i][j];
actualSum += (2 * table[i][j]);
}
}
}
}
void flipLines(int table[16][16], int N, int M,
vector<int> cols, long long& actualSum) {
for(int j = 0; j < M; ++j) {
if(cols[j] == 1) {
for(int i = 0; i < N; ++i) {
table[i][j] = -table[i][j];
actualSum += (2 * table[i][j]);
}
}
}
}
int main() {
ifstream fin ("flip.in");
ofstream fout("flip.out");
int N,M; fin >> N >> M;
int table[16][16];
long long maxSum = 0;
long long initialSum = 0;
for(int i = 0; i < N; ++i) {
for(int j = 0; j < M; ++j) {
fin >> table[i][j];
initialSum += table[i][j];
}
}
maxSum = initialSum;
for(int i = 0; i <= N; ++i) {
vector<int> lines;
for(int j = N - 1; j >= 0; --j) {
if(j < i) {
lines.push_back(1);
}
else {
lines.push_back(0);
}
}
for(int j = 0; j <= M; ++j) {
vector<int> cols;
for(int k = M - 1; k >= 0; --k) {
if(k < j) {
cols.push_back(1);
}
else {
cols.push_back(0);
}
}
// here solution
long long actualSum = initialSum;
do{
vector<int> newCols (cols);
do{
flipCols(table, N, M, lines, actualSum);
flipLines(table, N, M, newCols, actualSum);
maxSum = max(maxSum, actualSum);
flipCols(table, N, M, lines, actualSum);
flipLines(table, N, M, newCols, actualSum);
/*
cout << "\nlines:";
for(int p = 0; p < N; ++p) {
cout << lines[p];
}
cout << "\ncols:";
for(int p = 0; p < M; ++p) {
cout << newCols[p];
} */
}while(next_permutation(newCols.begin(), newCols.end()));
// cout <<"\n-----------\n";
}while(next_permutation(lines.begin(), lines.end()));
}
}
fout << maxSum << "\n";
return 0;
}