Cod sursa(job #1303249)
Utilizator | Alexandru Bunget ioalexno1 | Data | 27 decembrie 2014 19:42:51 |
---|---|---|---|
Problema | Jocul Flip | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Teme Pregatire ACM Unibuc 2014, Anul II | Marime | 1.45 kb |
#include <cstdio>
using namespace std;
const int MAX_N = 20;
int a[MAX_N][MAX_N], st[MAX_N];
int main()
{
freopen("flip.in", "r", stdin);
int n, m;
scanf("%d %d\n", &n, &m);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
scanf("%d", &a[i][j]);
fclose(stdin);
int k = 1, sol = -1e9;
st[1] = -1;
bool as;
while(k > 0){
if(st[k] < 1){
as = true;
++st[k];
}
else as = false;
if(as){
if(k == m){
for(int i = 1; i <= k; ++i)
if(st[i] == 1)
for(int j = 1; j <= n; ++j)
a[j][i] *= -1;
int sum = 0;
for(int i = 1; i <= n; ++i){
int s = 0;
for(int j = 1; j <= m; ++j)
s += a[i][j];
if(s > 0)
sum += s;
else
sum -= s;
}
if(sum > sol)
sol = sum;
}
else
st[++k] = -1;
}
else {
--k;
if(st[k] == 1)
for(int i = 1; i <= n; ++i)
a[i][k] *= -1;
}
}
freopen("flip.out", "w", stdout);
printf("%d", sol);
fclose(stdout);
return 0;
}