Cod sursa(job #1377810)

Utilizator laurenttlaurentiu pavel laurentt Data 6 martie 2015 05:38:17
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#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;
}