Cod sursa(job #1519223)

Utilizator serbanSlincu Serban serban Data 7 noiembrie 2015 00:05:31
Problema Jocul Flip Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <bits/stdc++.h>

using namespace std;

long long a[20][20], c[20], l[20];

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

    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            cin >> a[i][j], c[j] += a[i][j], l[i] += a[i][j];

    bool ok = true;
    while(ok) {
        ok = false;
        long long mx = 0, w = 0, poz = 0;
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= m; j ++) {
                if(-l[i] > mx) {
                    mx = -l[i];
                    poz = i; w = 0;
                }
                if(-c[j] > mx) {
                    mx = -c[j];
                    poz = j; w = 1;
                }
            }
        if(mx) {
            ok = true;
            if(w == 0) {
                l[poz] = -l[poz];
                for(int j = 1; j <= m; j ++)
                    c[j] -= a[poz][j], a[poz][j] = -a[poz][j], c[j] += a[poz][j];
            }
            if(w == 1) {
                c[poz] = -c[poz];
                for(int i = 1; i <= n; i ++)
                    l[i] -= a[i][poz], a[i][poz] = -a[i][poz], l[i] += a[i][poz];
            }
        }
    }
    long long s = 0;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            s += a[i][j];
    cout << s << "\n";
    return 0;
}