Cod sursa(job #1116740)

Utilizator SmarandaMaria Pandele Smaranda Data 22 februarie 2014 19:36:30
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <fstream>
#include <cstdlib>
#include <cstring>


using namespace std;

ifstream fin ("flip.in");
ofstream fout ("flip.out");

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

void read () {
    long i, j;
    fin >> n >> m;
    for (i = 0; i < n; i ++)
        for (j = 0; j < m; j ++) {
            fin >> a [i][j];
            c [i][j] = a [i][j];
        }
}

void flip (long l) {
    long j;
    for (j = 0; j < m; j ++)
        a [l][j] = a [l][j] * (-1);
}

void solve () {
    long s, b, i, j, max = -1, S, ns;
    ns = (1 << n) - 1;
    for (s = 0; s <= ns; s ++) {
        for (b = 0; b < n; b ++)
            if (s & (1 << b))
                flip (b);
        for (j = 0; j < m; j ++) {
            S = 0;
            for (i = 0; i < n; i ++)
                S = S + a [i][j];
            if (S < 0) {
                S = 0;
                for (i = 0; i < n; i ++)
                    a [i][j] = a [i][j] * (-1);
            }
        }
        S = 0;
        for (i = 0; i < n; i ++)
            for (j = 0; j < m; j ++)
                S = S + a [i][j];
        if (S > max)
            max = S;
        memcpy (a, c, sizeof (a));
    }
    fout << max << "\n";
}

int main () {
    long i, j, k, h;
    read ();
    solve ();
  /*  fout << "16 16\n";
    for (i = 1; i <= 16; i ++) {
        for (j = 1; j <= 16; j ++) {
            k = rand () % 1000001;
            h = rand () % 2;
            if (h == 0)
                fout << k << " ";
            else fout << -k << " ";
        }
        fout << "\n";
    }*/
    return 0;
}