Pagini recente » Cod sursa (job #764360) | Cod sursa (job #2483932) | Cod sursa (job #1090163) | Cod sursa (job #1913936) | Cod sursa (job #2192761)
#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;
}
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 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;
}
std::vector<int> flippedCols = std::vector<int>();
for (int j = 0; j < m; j++) {
int diff= flipCol(table, j);
if (diff > 0) {
currentSum += diff;
flippedCols.push_back(j);
} else {
flipCol(table, j);
}
}
if (currentSum > maxSum) {
maxSum = currentSum;
}
for (int j = 0; j < flippedCols.size(); j++) {
currentSum += flipCol(table, j);
}
rowStack.push_back(-1);
} else {
flipCol(table, rowStack[rowStack.size() - 1]);
rowStack.pop_back();
}
}
out << maxSum;
return 0;
}