Pagini recente » Borderou de evaluare (job #1760255) | Borderou de evaluare (job #1152901) | Cod sursa (job #1988450) | Cod sursa (job #2966382) | Cod sursa (job #765267)
Cod sursa(job #765267)
#include <fstream>
#include <iostream>
#define SIZE_LIMIT 16
#define COLUMNS false
#define ROWS true
int stack[SIZE_LIMIT];
int stackSize;
int matrix[SIZE_LIMIT][SIZE_LIMIT];
int rows, columns;
bool type;
int getMaxSumOf(void)
{
int result = 0;
if(type == COLUMNS)
{
for(int i = 0; i < stackSize; ++i)
for(int j = 0; j < rows; ++j)
matrix[j][stack[i]] *= -1;
for(int i = 0; i < rows; ++i)
{
int partialResult = 0;
for(int j = 0; j < columns; ++j)
partialResult += matrix[i][j];
result += (partialResult < 0 ? -partialResult : partialResult);
}
for(int i = 0; i < stackSize; ++i)
for(int j = 0; j < rows; ++j)
matrix[j][stack[i]] *= -1;
}
else
{
for(int i = 0; i < stackSize; ++i)
for(int j = 0; j < columns; ++j)
matrix[stack[i]][j] *= -1;
for(int i = 0; i < columns; ++i)
{
int partialResult = 0;
for(int j = 0; j < rows; ++j)
partialResult += matrix[j][i];
result += (partialResult < 0 ? -partialResult : partialResult);
}
for(int i = 0; i < stackSize; ++i)
for(int j = 0; j < columns; ++j)
matrix[stack[i]][j] *= -1;
}
return result;
}
int main(void)
{
stackSize = 0;
int stackIndex = 0;
type = COLUMNS;
std::ifstream in("flip.in");
in >> rows >> columns;
for(int i = 0; i < rows; ++i)
for(int j = 0; j < columns; ++j)
in >> matrix[i][j];
in.close();
int limit;
if(rows > columns)
{
limit = rows - 1;
type = ROWS;
}
else
limit = columns - 1;
int globalMaximumSum = getMaxSumOf();
while(++stackSize <= limit + 1)
{
stackIndex = 0;
for(;;)
{
if(!stackIndex)
stack[stackIndex] = 0;
else
stack[stackIndex] = stack[stackIndex - 1] + 1;
if(stackIndex < stackSize - 1)
++stackIndex;
else
{
while(stack[stackIndex] <= limit)
{
int temp = getMaxSumOf();
if(temp > globalMaximumSum)
globalMaximumSum = temp;
++stack[stackIndex];
}
stackIndex--;
if(stackIndex < 0)
break;
while(limit - ++stack[stackIndex] < stackSize - stackIndex - 1 && stackIndex >= 0) stackIndex--;
if(stackIndex < 0)
break;
++stackIndex;
}
}
}
std::ofstream out("flip.out");
out << globalMaximumSum << '\n';
out.close();
return 0;
}