Pagini recente » Cod sursa (job #760215) | Cod sursa (job #639578) | Cod sursa (job #1790378) | Cod sursa (job #1313161) | Cod sursa (job #1377810)
#include<fstream>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
long long absolute(long long x) {
return (x < 0)? (-x) : (x);
}
long long getSum(int table[16][16], int N, int M) {
long long sum = 0;
for(int i = 0; i < M; ++i) {
long long sumCol = 0;
for(int j = 0; j < N; ++j) {
sumCol += table[j][i];
}
sum += absolute(sumCol);
}
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> 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];
}
}
}
}
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);
}
}
// here solution
long long actualSum = initialSum;
do{
flipLines(table, N, M, lines, actualSum);
maxSum = max(maxSum, getSum(table,N,M));
flipLines(table, N, M, lines, actualSum);
/*
cout << "maxSum" << maxSum <<"\nlines:";
for(int p = 0; p < N; ++p) {
cout << lines[p];
}
cout << "\n";
*/
}while(next_permutation(lines.begin(), lines.end()));
}
fout << maxSum << "\n";
return 0;
}