Cod sursa(job #1862878)

Utilizator RaresEGaySopterean Adrian RaresEGay Data 30 ianuarie 2017 13:19:34
Problema Jocul Flip Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <fstream>
#include <stdlib.h>

#define INF 0x3f3f3f3f

using namespace std;

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

int n, m, v[17][17], s[17], used[17];
long long maxSum, absSum, maxFlip = -INF, lineSum[17];

int next(int k){
    if(s[k] < m){
        s[k]++;
        return 1;
    }
    return 0;
}

int condition(int k){
    for(int i=1; i<k; ++i)
        if(s[i] >= s[k]) return 0;
    return 1;
}

void flip(int c){
    maxSum = 0;
    for(int i=1; i<=c; ++i){
        used[s[i]] = 1;
    }

    for(int i=1; i<=n; ++i){
        absSum = 0;
        for(int j=1; j<=m; ++j){
            if(used[j] == 1){
                absSum += -v[i][j];
            }
            else absSum += v[i][j];
        }
        maxSum += abs(absSum);
    }

    for(int i=1; i<=c; ++i){
        used[s[i]] = 0;
    }

    if(maxSum > maxFlip) maxFlip = maxSum;

}


void bktr(int k, int c){
    s[k] = 0;
    while(next(k)){
        if(condition(k)){
            if(k == c) flip(c);
            else bktr(k+1, c);
        }
    }
}

int main(){
    f >> n >> m;
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j){
            f >> v[i][j];
        }

    for(int i=1; i<=m; ++i)
        bktr(1, i);

    g << maxFlip << '\n';
}