Pagini recente » Cod sursa (job #3322996) | Cod sursa (job #3329240) | Cod sursa (job #3342622) | Cod sursa (job #2118703) | Cod sursa (job #3311503)
#include <iostream>
#include <fstream>
using namespace std;
void helloWorld() {
const auto lang = "C++";
cout << "Hello and welcome to " << lang << "!\n";
for (int i = 1; i <= 5; i++) {
cout << "i = " << i << endl;
}
}
/*
*FLIP: inmulteste linii, coloane cu -1 asa incat sa ajungi la suma cea mai mare
*
*problema: pot strica toate nr de pe prima linie si sa reintorc semnu la primu numar daca inmultesc
*coloana 1
*
*
*/
ifstream fin;
ofstream fout;
int n, m;
//matricea de semne
int s[17][17];
int a[17][17];
//status per lin daca a fost flipped sau nu
int r[17], c[17];
int sum_max;
void update_sum() {
//stim ca c[j] e semnul de la suma randului
int sum_temp = 0;
for (int j = 1; j <= m; ++j) {
for (int i = 1; i <= n; ++i) {
sum_temp += r[i] * a[i][j];
}
c[j] = sum_temp >= 0 ? 1 : -1;
}
int sum = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
sum += a[i][j] * r[i] * c[j];
}
}
sum_max = sum > sum_max ? sum : sum_max;
}
void pb_read() {
fin.close();
fin.open("flip.in");
fout.close();
fout.open("flip.out");
}
int main() {
fin.open("text.in");
fout.open("text.out");
pb_read();
fin >> n >> m;
//matricea de semne + prima linie pe care am macar un nr nenul
int k = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
fin >> a[i][j];
s[i][j] = a[i][j] > 0 ? 1 : a[i][j] == 0 ? 0 : -1;
if (!k && a[i][j] != 0) k = i;
}
}
//daca toata matricea e 0 am inchis
if (!k) {
fout << 0 << '\n';
return 0;
}
//backtracking pentru toate combinatiile de -1 si 1 pentru r[i]
for (int i = 0; i < (1 << n); ++i) { //mergem de la 0 la 2^n - 1
for (int j = 0; j < n; ++j) { //daca bit-ul j de la i este 0 atunci il face 1 altfel 0
r[j + 1] = (i & (1 << j)) ? -1 : 1;
}
update_sum();
}
fout << sum_max << '\n';
return 0;
}