Pagini recente » Cod sursa (job #2782914) | Istoria paginii runda/azidela18simularea/clasament | Cod sursa (job #177629) | Cod sursa (job #410318) | Cod sursa (job #1861531)
#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];
long long maxSum, maxFlip = -INF, lineSum[17], maxLine;
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){
long long abSum;
maxSum = maxLine;
for(int i=1; i<=c; ++i){
maxSum -= lineSum[i];
abSum = 0;
for(int j=1; j<=n; ++j)
abSum -= v[j][s[i]];
maxSum += abs(abSum);
}
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];
lineSum[i] += v[i][j];
}
maxLine += lineSum[i];
}
for(int i=1; i<=m; ++i)
bktr(1, i);
g << maxFlip << '\n';
}