Pagini recente » Cod sursa (job #1478457) | Cod sursa (job #1854666) | Cod sursa (job #1062131) | Monitorul de evaluare | Cod sursa (job #1205344)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
int main() {
int total = 0;
ifstream in("flip.in");
ofstream out("flip.out");
int n,m;
in >> n >> m;
vector< pair<int, int > > sum;
int* matrix = new int[m*n];
for (int i = 0; i < n; i++) {
int s = 0;
for (int j = 0 ; j< m; j++) {
in >> matrix[i*m + j];
s += matrix[i*m + j];
}
sum.push_back(make_pair(s, i));
total += s;
}
for (int j = 0; j < m; j++) {
int s = 0;
for (int i = 0; i < n; i++) {
s += matrix[i*m + j];
}
sum.push_back(make_pair(s, j + n));
total += s;
}
total /= 2;
sort(sum.begin(), sum.begin() + m + n);
while (sum[0].first < 0) {
total -= 2*sum[0].first;
if (sum[0].second < n) { // flip linie
for (int i = 1; i < n + m; i++) {
if (sum[i].second >= n) {
sum[i].second -= 2* matrix[sum[0].second*m+sum[i].second-n];
}
}
}
else { // flip coloana
for (int i = 1; i < n + m; i++) {
if (sum[i].second != -1 && sum[i].second < n) {
sum[i].second -= 2* matrix[sum[i].second*m+sum[0].second-n];
}
}
}
sum[0].first = 0;
sum[0].second = -1;
sort(sum.begin(), sum.begin() + m + n);
}
out << total;
in.close();
out.close();
return 0;
}