Pagini recente » Cod sursa (job #3219336) | Cod sursa (job #2898152) | Cod sursa (job #3170813) | Cod sursa (job #2299228) | Cod sursa (job #2198942)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("flip.in");
ofstream fout("flip.out");
int n,m,flip[40],Q; // matricea flip tine 1 - 17 : linii, de la 18 -> tine coloane
int matrix[17][17];
bool used[33];
int sum,maxsum;
int initial[40],final[40];
void bkt(int poz) {
if(poz == Q + 1) {
maxsum = max(sum, maxsum);
return;
} else {
for(int i = flip[poz - 1]; i <= n + m; i++) {
if(!used[i]) {
flip[poz] = i;
sum -= initial[i];
sum += final[i];
used[i] = true;
bkt(poz + 1); //de aici in jos reinitializem tot, inclusiv suma.
sum += initial[i];
sum -= final[i];
used[i] = false;
}
}
}
}
int main() {
fin >> n >> m;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
fin >> matrix[i][j];
sum += matrix[i][j];
}
}
maxsum = sum;
int k = 0;
for(int i = 1; i <= n; i++) {
k++;
for(int j = 1; j <= m; j++) {
initial[k] += matrix[i][j];
final[k] += (matrix[i][j] * (-1));
}
}
for(int j = 1; j <= m; j++) {
k++;
for(int i = 1; i <= n; i++) {
initial[k] += matrix[i][j];
final[k] += (matrix[i][j] * (-1));
}
}
flip[0] = 1;
for(Q = 1; Q <= n + m; Q++) {
bkt(1);
}
fout << maxsum;
}