Pagini recente » Cod sursa (job #2753823) | Cod sursa (job #2579209) | Cod sursa (job #1864081) | Cod sursa (job #2864352) | Cod sursa (job #1862878)
#include <fstream>
#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[17];
long long maxSum, absSum, maxFlip = -INF, lineSum[17];
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;
return 1;
}
void flip(int c){
maxSum = 0;
for(int i=1; i<=c; ++i){
used[s[i]] = 1;
}
for(int i=1; i<=n; ++i){
absSum = 0;
for(int j=1; j<=m; ++j){
if(used[j] == 1){
absSum += -v[i][j];
}
else absSum += v[i][j];
}
maxSum += abs(absSum);
}
for(int i=1; i<=c; ++i){
used[s[i]] = 0;
}
if(maxSum > maxFlip) maxFlip = maxSum;
}
void bktr(int k, int c){
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';
}