Pagini recente » Cod sursa (job #2752925) | Cod sursa (job #1875940) | Cod sursa (job #2637664) | Cod sursa (job #1571488) | Cod sursa (job #2324019)
#include <stdlib.h>
#include <stdint.h>
#include <string>
#include <vector>
#include <iostream>
#include <unordered_map>
#include <memory>
#include <algorithm>
#include <deque>
#include <iterator>
#include <numeric>
#include <assert.h>
#include <cstdlib>
#include <sstream>
#include <fstream>
#define INPUT_PATH ""
#define OUTPUT_PATH ""
void algorithm();
int main()
{
algorithm();
return 0;
}
using namespace std;
namespace
{
////////////////////////////////////////////////////////////////////////////////
vector<int> fillRowSums(
const vector<int>& matrix,
const int nrRows,
const int nrCols)
{
vector<int> rowSums(nrRows, 0);
for (int row = 0; row < nrRows; ++row)
{
int rowSum = 0;
for (int col = 0; col < nrCols; ++col)
{
rowSum += matrix[row*nrCols + col];
}
rowSums[row] = rowSum;
}
return rowSums;
}
////////////////////////////////////////////////////////////////////////////////
vector<int> fillColSums(
const vector<int>& matrix,
const int nrRows,
const int nrCols)
{
vector<int> colSums(nrCols, 0);
for (int col = 0; col < nrCols; ++col)
{
int colSum = 0;
for (int row = 0; row < nrRows; ++row)
{
colSum += matrix[row*nrCols + col];
}
colSums[col] = colSum;
}
return colSums;
}
////////////////////////////////////////////////////////////////////////////////
void flipRow(
vector<int>& matrix,
const int rowToFlip,
const int nrRows,
const int nrCols)
{
for (int col = 0; col < nrCols; ++col)
{
matrix[rowToFlip*nrCols + col] *= -1;
}
}
////////////////////////////////////////////////////////////////////////////////
void flipCol(
vector<int>& matrix,
const int colToFlip,
const int nrRows,
const int nrCols)
{
for (int row = 0; row < nrRows; ++row)
{
matrix[row*nrCols + colToFlip] *= -1;
}
}
}
////////////////////////////////////////////////////////////////////////////////
void algorithm()
{
ifstream inputFile(INPUT_PATH "flip.in");
ofstream outputFile(OUTPUT_PATH "flip.out");
int nrRows = 0; inputFile >> nrRows;
int nrCols = 0; inputFile >> nrCols;
vector<int> matrix;
matrix.reserve(nrRows*nrCols);
int readVal = 0;
while (inputFile >> readVal)
{
matrix.push_back(readVal);
}
int sum = accumulate(matrix.begin(), matrix.end(), 0);
int sumBeforeFlip = sum - 1;
while (sum > sumBeforeFlip)
{
sumBeforeFlip = sum;
vector<int> rowSums = fillRowSums(matrix, nrRows, nrCols);
vector<int> colSums = fillColSums(matrix, nrRows, nrCols);
vector<int>::iterator itMinRow = min_element(begin(rowSums), end(rowSums));
vector<int>::iterator itMinCol = min_element(begin(colSums), end(colSums));
if (*itMinRow < *itMinCol)
{
flipRow(matrix, itMinRow - begin(rowSums), nrRows, nrCols);
}
else
{
flipCol(matrix, itMinCol - begin(colSums), nrRows, nrCols);
}
sum = accumulate(matrix.begin(), matrix.end(), 0);
}
outputFile << sumBeforeFlip;
inputFile.close();
outputFile.close();
}