Cod sursa(job #1642756)

Utilizator bogdan10bosBogdan Sitaru bogdan10bos Data 9 martie 2016 16:00:22
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <bits/stdc++.h>

using namespace std;

#define FILE_IO

int n, m, i, j, ans;
int c[20][2];
int a[20][20];

void bck(int step, int lst)
{
    int s = 0;
    for(int i = 1; i <= m; i++)
        s += max(c[i][0] - c[i][1], c[i][1] - c[i][0]);
    ans = max(s, ans);

    for(int nxt = lst + 1; nxt <= n; nxt++)
    {
        for(int i = 1; i <= m; i++)
        {
            c[i][0] -= a[nxt][i];
            c[i][1] += a[nxt][i];
        }

        bck(step + 1, nxt);

        for(int i = 1; i <= m; i++)
        {
            c[i][0] += a[nxt][i];
            c[i][1] -= a[nxt][i];
        }
    }
}

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

    scanf("%d%d", &n, &m);
    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++)
        {
            scanf("%d", &a[i][j]);
            if(a[i][j] > 0) c[j][0] += a[i][j];
            else c[j][1] -= a[i][j];
        }

    ans = -(1 << 30);
    bck(1, 0);
    printf("%d", ans);

    return 0;
}