Cod sursa(job #1303249)

Utilizator ioalexno1Alexandru Bunget ioalexno1 Data 27 decembrie 2014 19:42:51
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul II Marime 1.45 kb
#include <cstdio>

using namespace std;

const int MAX_N = 20;
int a[MAX_N][MAX_N], st[MAX_N];

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

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

    fclose(stdin);
    int k = 1, sol = -1e9;
    st[1] = -1;
    bool as;
    while(k > 0){

        if(st[k] < 1){

            as = true;
            ++st[k];
        }
        else as = false;
        if(as){

            if(k == m){
                for(int i = 1; i <= k; ++i)
                    if(st[i] == 1)
                        for(int j = 1; j <= n; ++j)
                            a[j][i] *= -1;
                int sum = 0;
                for(int i = 1; i <= n; ++i){

                    int s = 0;
                    for(int j = 1; j <= m; ++j)
                        s += a[i][j];
                    if(s > 0)
                        sum += s;
                    else
                        sum -= s;
                }
                if(sum > sol)
                    sol = sum;
            }
            else
                st[++k] = -1;
        }
        else {

            --k;
            if(st[k] == 1)
                for(int i = 1; i <= n; ++i)
                    a[i][k] *= -1;
        }
    }
    freopen("flip.out", "w", stdout);
    printf("%d", sol);
    fclose(stdout);
    return 0;
}