Pagini recente » Cod sursa (job #949863) | Cod sursa (job #386877) | Cod sursa (job #29026) | Cod sursa (job #390658) | Cod sursa (job #1864642)
#include <fstream>
#include <iostream>
#include <stdlib.h>
#define INF 0x3f3f3f3f
using namespace std;
ifstream f("flip.in");
ofstream g("flip.out");
int n, m, v[17][17], s[17], used[70000][17];
long long maxSum, absSum, maxFlip = -INF, p;
int next(int k){
if(s[k] < m){
s[k]++;
return 1;
}
return 0;
}
int condition(int k){
for(int i=1; i<k; ++i)
if(s[i] >= s[k]) return 0;
used[p][s[k]] = 1;
return 1;
}
void flip(int c){
maxSum = 0;
for(int i=1; i<=n; ++i){
absSum = 0;
for(int j=1; j<=m; ++j){
if(used[p][j]){
absSum += -v[i][j];
}
else absSum += v[i][j];
}
maxSum += abs(absSum);
}
if(maxSum > maxFlip) maxFlip = maxSum;
}
void bktr(int k, int c){
++p;
s[k] = 0;
while(next(k)){
if(condition(k)){
if(k == c) flip(c);
else bktr(k+1, c);
}
}
}
int main(){
f >> n >> m;
for(int i=1; i<=n; ++i)
for(int j=1; j<=m; ++j){
f >> v[i][j];
}
for(int i=1; i<=m; ++i)
bktr(1, i);
g << maxFlip << '\n';
}