Cod sursa(job #367857)

Utilizator LaurDLaur Dimana LaurD Data 23 noiembrie 2009 17:50:29
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <iostream>

int n, m, st[ 17 ], k;
long A[ 17 ][ 17 ], smax = -999999;

void Read()
{
    FILE *in = fopen( "flip.in", "r" );

    fscanf( in, "%d %d", &n, &m );
    for ( int i = 0; i < n; i++ )
        for ( int j = 0; j < m; j++ )
            fscanf( in, "%ld", &A[ i ][ j ]  );

    fclose( in );
}

int Successor()
{
    if ( st[ k ] < 0 )
    {
        st[ k ] += 2;
        return 1;
    }

    return 0;
}

void Type()
{
    int ch[ 17 ];
    long s;

    for ( int j = 0; j < m; j++ )
    {
        s = 0;
        for ( int i = 0; i < n; i++ )
        {
            s += st[ i ] * A[ i ][ j ];
        }

        ch[ j ] = s < 0 ? -1 : 1;
    }

    s = 0;
    for ( int i = 0; i < n; i++ )
        for ( int j = 0; j < m; j++ )
            s += st[ i ] * A[ i ][ j ] * ch[ j ];

    if ( s > smax )
        smax = s;
}

void Solve()
{
    int as;

    k = 0;
    st[ k ] = -3;

    do
    {
        as = Successor();

        if ( as )
        {
            if ( k == n )
                Type();
            else
            {
                k++;
                st[ k ] = -3;
            }
        }
        else
            k--;
    }
    while ( k > 0 );
}

void Write()
{
    FILE *out = fopen( "flip.out", "w" );

    fprintf( out, "%ld", smax );

    fclose( out );
}

int main( void )
{
    Read();
    Solve();
    Write();

    return 0;
}