Cod sursa(job #1609756)

Utilizator cameleonGeorgescu Dan cameleon Data 22 februarie 2016 23:28:31
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <cstdio>
#include<iostream>
#include <fstream>
using namespace std;

int n, m , a[18][18], i, j, s1[18], s2[18],nr,p,k, z, x[18], semn;
int total, maxim;

int main()
{
    freopen("flip.in","r",stdin);
    freopen("flip.out","w",stdout);

    scanf("%d%d", &n, &m);

    for( i = 1; i <= n; i++)
        for( j = 1; j <= m; j++)
            scanf("%d",&a[i][j]);

    k = (1 << m) - 1;
     maxim = -(1<<30);
    //generez toate submultimile de ;a 0 la 2^m-1
    for( nr = 0; nr <= k; nr++){
        z = nr;  //z este o submultime si o transcriu intr-un vect caracteristic
        p = 1;
        while(z != 0)
        {
            if(z%2 == 1)
                {
                   x[p] = 1;
                }
            else
                x[p] = 0;
            p++;
            z /= 2;
        }
        // calculez sumele pe fiecare lini tinand cont ca toate coloanele corespunzatoare submultimii sunt cu -1
        //suma pe o linie se calculeaza considerand toata linia cu (s1) si considerand toata linia cu -(s2)
        total = 0;
        for( i = 1; i <= n; i++)
        {
            s1[i] = s2[i] =0;
            for(j = 1; j <= m; j++)
                {
                    if( x[j] == 1) semn = -1;
                    else semn = 1;
                    s1[i] = s1[i] + semn *a[i][j];
                    s2[i] = s2[i] - semn*a[i][j];
                }
                total += max(s1[i], s2[i]); //adaugam la total varianta cea mai mare
        }

        maxim = max(total, maxim);

    }
    printf("%d", maxim);

       return 0;

   }