Pagini recente » Cod sursa (job #2755893) | Cod sursa (job #988218) | Cod sursa (job #1829763) | Cod sursa (job #2797877) | Cod sursa (job #2192759)
#include <fstream>
#include <vector>
long flipRow(std::vector<std::vector<int>>& table, int row) {
long oldSum = 0, newSum = 0;
for (int j = 0; j < table[row].capacity(); j++) {
oldSum += table[row][j];
table[row][j] *= -1;
newSum += table[row][j];
}
return newSum - oldSum;
}
long flipCol(std::vector<std::vector<int>>& table, int col) {
long oldSum = 0, newSum = 0;
for (int i = 0; i < table.capacity(); i++) {
oldSum += table[i][col];
table[i][col] *= -1;
newSum += table[i][col];
}
return newSum - oldSum;
}
bool isValid(std::vector<int> stack, int size) {
if (stack.size() >= size + 1) return false;
if (stack[stack.size() - 1] >= size) return false;
if (stack[stack.size() - 1] < 0) return false;
if (stack.size() >= 2 && stack[stack.size() - 1] <= stack[stack.size() - 2]) return false;
return true;
}
long backtrackRows(std::vector<std::vector<int>>& table, long currentSum, int n) {
long maxSum = currentSum;
std::vector<int> rowStack = std::vector<int>();
rowStack.push_back(-1);
while (rowStack.size() != 0) {
bool found = false;
if (rowStack[rowStack.size() - 1] >= 0) {
currentSum += flipRow(table, rowStack[rowStack.size() - 1]);
}
while (rowStack[rowStack.size() - 1] < n) {
rowStack[rowStack.size() - 1]++;
if (isValid(rowStack, n)) {
found = true;
break;
}
}
if (found) {
currentSum += flipRow(table, rowStack[rowStack.size() - 1]);
if (currentSum > maxSum) {
maxSum = currentSum;
}
rowStack.push_back(-1);
} else {
flipCol(table, rowStack[rowStack.size() - 1]);
rowStack.pop_back();
}
}
return maxSum;
}
long backtrackCols(std::vector<std::vector<int>>& table, long currentSum, long (*backtrackRows)(std::vector<std::vector<int>>&, long, int), int n, int m) {
long maxSum = currentSum;
std::vector<int> colStack = std::vector<int>();
colStack.push_back(-1);
while (colStack.size() != 0) {
bool found = false;
if (colStack[colStack.size() - 1] >= 0) {
currentSum += flipCol(table, colStack[colStack.size() - 1]);
}
while (colStack[colStack.size() - 1] < m) {
colStack[colStack.size() - 1]++;
if (isValid(colStack, m)) {
found = true;
break;
}
}
if (found) {
currentSum += flipCol(table, colStack[colStack.size() - 1]);
if (currentSum > maxSum) {
maxSum = currentSum;
}
long newSum = backtrackRows(table, currentSum, m);
if (newSum > maxSum) {
maxSum = newSum;
}
colStack.push_back(-1);
} else {
flipCol(table, colStack[colStack.size() - 1]);
colStack.pop_back();
}
}
return maxSum;
}
int main() {
std::ifstream in("flip.in");
std::ofstream out("flip.out");
int n, m;
in >> n >> m;
std::vector<std::vector<int>> table = std::vector<std::vector<int>>();
table.reserve(n);
for (int i = 0; i < n; i++) {
table[i] = std::vector<int>();
table[i].reserve(m);
}
long currentSum = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
in >> table[i][j];
currentSum += table[i][j];
}
}
long max1 = backtrackCols(table, currentSum, backtrackRows, n, m);
long max2 = backtrackRows(table, currentSum, n);
out << (max1 > max2 ? max1 : max2);
return 0;
}