Cod sursa(job #1864642)

Utilizator RaresEGaySopterean Adrian RaresEGay Data 31 ianuarie 2017 21:32:46
Problema Jocul Flip Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>
#include <iostream>
#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[70000][17];
long long maxSum, absSum, maxFlip = -INF, p;

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;
    used[p][s[k]] = 1;
    return 1;
}

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


    if(maxSum > maxFlip) maxFlip = maxSum;

}


void bktr(int k, int c){
    ++p;
    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';
}