Pagini recente » Cod sursa (job #1840854) | Cod sursa (job #1182572) | Cod sursa (job #265523) | Cod sursa (job #2885047) | Cod sursa (job #2463466)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("flip.in");
ofstream g("flip.out");
#define MAX_SIZE 17
int n, m, i, j, k, nextline, nextcolumn, index, done;
int table[MAX_SIZE][MAX_SIZE];
int sumlin[MAX_SIZE];
int sumcol[MAX_SIZE];
long int summin, suma, prevsum = -1000000000, sum = -999999999, summax = -1000000000;
bool minIsLine;
int SearchLinesAndColumns() {
summin = sumlin[1];
for(i = 2; i <= n; i++) {
if(sumlin[i] < summin) {
summin = sumlin[i];
index = i;
minIsLine = true;
}
}
for(j = 1; j <= m; j++) {
if(sumcol[j] < summin) {
summin = sumcol[j];
index = j;
minIsLine = false;
}
}
if(summin < 0)
return index;
return -1;
}
void ChangeLine(int nextline) {
sumlin[nextline] = -sumlin[nextline];
for(j = 1; j <= m; j++) {
table[nextline][j] = -table[nextline][j];
sumcol[j] += 2*table[nextline][j];
}
}
void ChangeColumn(int nextcolumn) {
sumcol[nextcolumn] = -sumcol[nextcolumn];
for(i = 1; i <= n; i++) {
table[i][nextcolumn] = -table[i][nextcolumn];
sumlin[i] += 2*table[i][nextcolumn];
}
}
int main()
{
f >> n >> m;
for(i = 1; i <= n; i++) {
for(j = 1; j <= m; j++) {
f >> table[i][j];
sumlin[i] += table[i][j];
sumcol[j] += table[i][j];
}
}
while(prevsum <= sum && index != -1) {
index = SearchLinesAndColumns();
if(index != -1) {
if(minIsLine)
ChangeLine(index);
else ChangeColumn(index);
prevsum = sum;
sum = 0;
for(i = 1; i <= n; i++)
sum += sumlin[i];
if(sum > summax)
summax = sum;
}
}
g << summax;
return 0;
}