Cod sursa(job #899875)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 28 februarie 2013 16:43:04
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <fstream>

using namespace std;

const int MAX_N = 18;

int N, M, Max = -999999999;
int A[ MAX_N ][ MAX_N ], v[ MAX_N ];

inline void back(int k)
{
    if(k > N)
    {
        int s1 = 0, s2 = 0, sum = 0, t = 0;
        for(int j = 1; j <= M; ++j)
        {
            s1 = s2 = 0;
            for(int i = 1; i <= N; ++i)
            {
                if(v[i])
                    t = -A[i][j];
                else t = A[i][j];
                s1 += t, s2 += (-1) * t;
            }
            if(s1 > s2)
                sum += s1;
            else sum += s2;
        }
        if(sum > Max)
            Max = sum;
    }
    else
    {
        v[k] = 1, back(k+1);
        v[k] = 0, back(k+1);
    }
}

int main()
{
    ifstream f("flip.in");
    ofstream g("flip.out");

    f >> N >> M;
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= M; ++j)
            f >> A[i][j];

    back(1);

    g << Max << '\n';

    f.close();
    g.close();

    return 0;
}