Pagini recente » tema | Istoria paginii runda/temadivizori9_17_10 | Istoria paginii runda/lot_1 | Cod sursa (job #2127534) | Cod sursa (job #789887)
Cod sursa(job #789887)
#include <fstream>
#define DIM 16
#define MAX_DIM 1000001
struct MPos
{
int min, pos;
MPos(int min, int pos):min(min), pos(pos) {}
};
inline MPos findMin(int v[], int n)
{
MPos res(MAX_DIM, 0);
for(int i = 0; i < n; ++i) {
if (v[i] < res.min) {
res.min = v[i];
res.pos = i;
}
}
return res;
}
int main(void)
{
std::ifstream f("flip.in");
std::ofstream g("flip.out");
int N, M, sum = 0, dim;
int a[DIM][DIM], *sums;
MPos minim(-1, -1);
f >> N >> M;
dim = M + N;
sums = new int[N + M];
for(int i = 0; i < N; ++i) {
for(int j = 0; j < M; ++j) {
f >> a[i][j];
sums[i] += a[i][j];
sums[N + j] += a[i][j];
}
sum += sums[i];
}
minim = findMin(sums, dim);
while(minim.min < 0) {
if(minim.pos < N) {
for (int j = 0; j < M; ++j) {
int aux = a[minim.pos][j];
a[minim.pos][j] *= -1;
int diff = a[minim.pos][j] - aux;
sums[N + j] += diff;
sums[minim.pos] += diff;
sum += diff;
}
} else {
for (int i = 0; i < N; ++i) {
int pos = minim.pos - N;
int aux = a[i][pos];
a[i][pos] *= -1;
int diff = a[i][pos] - aux;
sums[N + pos] += diff;
sums[i] += diff;
sum += diff;
}
}
minim = findMin(sums, dim);
}
g << sum;
return 0;
}