Cod sursa(job #505390)

Utilizator idomiralinIdomir Alin idomiralin Data 2 decembrie 2010 00:37:24
Problema Jocul Flip Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
# include <stdlib.h>
# include <cstdio>

using namespace std;

int sol[100], m, n, a[100][100], s[100], sum, ct, max;
void back(int k)
{int i, j;
     if (k == m + 1)
     {
           for (i = 1; i <= m; i++)
               for (j = 1; j <= n; j++)
               if (sol[i]) a[i][j] = - a[i][j];
     
                sum = 0;
           for (i = 1; i <= n; i++)
               {
                    s[i] = 0;
                    for (j = 1; j <= m; j++)
                    s[i] += a[j][i];
                    if (s[i] < 0) s[i] = -s[i];
                    sum += s[i];
                    
                    if (max < sum) max = sum;
                     }
           }
     else
     {
         sol[k] = -1;
         while (sol[k] < 1)
         {
               sol[k]++;
               back(k + 1);
               }
         }
}
     
int main()
{int i, j;
    freopen("flip.in","r",stdin);
    freopen("flip.out","w",stdout);
    
    scanf("%d%d",&m,&n);
    for (i = 1; i <= m; i++)
        for (j = 1; j <= n; j++)
        scanf("%d",&a[i][j]);
    
    max = -1000000000;
    back(1);
    
    printf("%d",max);

return 0;
}