Cod sursa(job #2192761)

Utilizator georgeromanGeorge Roman georgeroman Data 7 aprilie 2018 10:39:25
Problema Jocul Flip Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#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;
}