Cod sursa(job #363533)

Utilizator ntargetDorin Mirea ntarget Data 13 noiembrie 2009 17:51:05
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <cstdio>
#include <cstring>

using namespace std;

#define FIN "flip.in"
#define FOUT "flip.out"
#define MAX_N 20

int A[MAX_N][MAX_N];
int S[MAX_N];
int V[MAX_N];
int BEST, N, M;

    void solve ()
    {
         int i, j, p;
         
         for (p = 0; p < 1 << N; ++p)
         {
             for (i = 1; i <= N; ++i)
                 if (p & (1 << (i - 1))) S[i] = 1; 
                                    else S[i] = 0;
             
             int vlue = 0;
             memset (V, 0, sizeof (V));
             
             for (j = 1; j <= M; ++j)
                 for (i = 1; i <= N; ++i)
                     if (S[i]) V[j] += A[i][j]; 
                          else V[j] -= A[i][j];
                     
             for (i = 1; i <= M; ++i)
                 if (V[i] > 0) vlue += V[i]; 
                          else vlue -= V[i];
                          
             if (vlue > BEST) BEST = vlue;
         }
         
         printf ("%d\n", BEST);
    }

    int main ()
    {
        freopen (FIN, "r", stdin);
        freopen (FOUT, "w", stdout);
        
        scanf ("%d %d", &N, &M);
        int i, j;
        
        for (i = 1; i <= N; ++i)
            for (j = 1; j <= M; ++j)
                scanf ("%d", A[i] + j);
        solve ();
        
        return 0;
    }