Cod sursa(job #1857109)

Utilizator AurelGabrielAurel Gabriel AurelGabriel Data 25 ianuarie 2017 20:23:22
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <fstream>


using namespace std;

int n, m;
long int a[16][16];

long int mx = -16000000;

int v[16];
const int u[2] = {-1 , 1};

long int calcMaxSum()
{
    long int s = 0;
    for(int i = 0; i < n; i++)
    {
        long int temp = 0;
        for(int j = 0; j < m; j++)
            temp+= a[i][j] * v[j];
        s+= max(temp, -temp);
    }
    return s;
}

void backtrack(int k)
{
    //if(k < n)
    for(int i = 0; i < 2; i++)
    {
        int temp = v[k];
        if(temp!= u[i])
        {
            v[k] = u[i];

            if(k == m-1)
            {
                /*for(int j = 0; j < m; j++)
                    cout << v[j] << ' ';
                cout << endl;*/
                mx = max(mx, calcMaxSum());
            }
            else
            backtrack(k+1);
        }
    }
}

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

    f >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            f >> a[i][j];

    backtrack(0);


    g << mx;


    return 0;
}