Cod sursa(job #75862)

Utilizator cos_minBondane Cosmin cos_min Data 6 august 2007 13:21:04
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <fstream>
#include <stdio.h>
using namespace std;

#define in "flip.in"
#define out "flip.out"
#define dim 17

int N, M;
int X[dim], Sel[dim];
int A[dim][dim];
long long maxim=0, t=0, sum=0;

int Ok(int);
void Back(int);

int main()
{
    X[0] = 0;
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    
    scanf("%d%d", &N, &M);
    for ( int i = 1; i <= N; i++ )
        for ( int j = 1; j <= M; j++ )
            scanf("%d", &A[i][j]), maxim += A[i][j];
    
    for ( int i = 1; i <= N; i++ )
    {
        sum = 0;
        for ( int j = 1; j <= M; j++ ) sum += A[i][j];

        if ( sum < 0 ) sum *= -1;
        t += sum;
    }
    
    if ( t > maxim ) maxim = t;      
    
    Back(1);
    
    printf("%lld", maxim);
}

void Back(int k)
{
     for ( int i = X[k-1]+1; i <= M; i++ )
     {
         X[k] = i;
         Sel[i] = 1;
         t = 0;
         if ( k <= M ) 
         {
              t = 0;
              for ( int i = 1; i <= N; i++ )
              {
                  sum = 0;    
                  for ( int j = 1; j <= M; j++ )
                  {
                      if ( Sel[j] ) sum += (-1)*A[i][j];
                      else          sum += A[i][j];
                  }
                  
                  if ( sum < 0 ) sum *= -1;
                  t += sum;
              }
              
              if ( t > maxim ) maxim = t;      
              
              if ( k < M ) Back(k+1);
         }
         Sel[i] = 0;
     }
}