Cod sursa(job #2022575)

Utilizator teodor440Teodor Tonghioiu teodor440 Data 16 septembrie 2017 19:04:41
Problema Jocul Flip Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>

using namespace std;

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

int n, m, flip[16][16], sumrow[16], sumcol[16], state[16][2];
long maxsum = -100000000;

void bkt2(int i, long suma){
    if(i >= m){
        if(suma > maxsum) maxsum = suma;
        return;
    }

    state[i][1] = 0;
    bkt2(i+1, suma);

    state[i][1] = 1;
    suma -= 2*sumcol[i];
    for(int j = 0; j < n; j++)
        if(state[j][0]) suma += 4*flip[j][i];
    bkt2(i+1, suma);
}

void bkt1(int i, long suma){
    if(i >= n){
        bkt2(0, suma);
        return;
    }

    state[i][0] = 0;
    bkt1(i+1, suma);

    state[i][0] = 1;
    suma -= 2*sumrow[i];
    bkt1(i+1, suma);
}

int main()
{
    int i, j, suma = 0;
    f >> n >> m;
    for(i = 0; i < n; i++)
        for(j = 0; j < m; j++)
            f >> flip[i][j];
    for(i = 0; i < n; i++)
        for(j = 0; j < m; j++){
            sumrow[i] += flip[i][j];
            sumcol[j] += flip[i][j];
            suma += flip[i][j];
        }

    bkt1(0, suma);

    g << maxsum;

    return 0;
}