Cod sursa(job #1462559)

Utilizator bogdanboboc97Bogdan Boboc bogdanboboc97 Data 18 iulie 2015 15:47:48
Problema Jocul Flip Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <fstream>
#include <limits>
using namespace std;
ifstream in("flip.in");
ofstream out("flip.out");
int a[20][20],n,m,mx,l[20],c[20];
void line(int x)
{
    for(int i=1;i<=n;i++)
    {
        a[x][0]-=a[x][i];
        a[0][i]-=a[x][i];
        a[x][i]=-a[x][i];
        a[x][0]+=a[x][i];
        a[0][i]+=a[x][i];
    }
}
void col(int x)
{
    for(int i=1;i<=m;i++)
    {
        a[0][x]-=a[i][x];
        a[i][0]-=a[i][x];
        a[i][x]=-a[i][x];
        a[0][x]+=a[i][x];
        a[i][0]+=a[i][x];
    }
}
int getsum()
{
    int sum=0;
    for(int i=1;i<=n;i++)
        sum+=a[i][0];
    return sum;
}
void back(int lastl)
{
    for(int i=1;i<=m;i++)
        if(a[0][i]<0)
        col(i);
    mx=max(mx,getsum());
    for(int i=lastl+1;i<=n;i++)
    if(l[i]==0){
            l[i]++;
            line(i);
            back(i);
            line(i);
            l[i]--;
    }
}
int main()
{
    in>>n>>m;
    mx=numeric_limits<int>::min();
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        in>>a[i][j];
        a[i][0]+=a[i][j];
        a[0][j]+=a[i][j];
    }
    back(0);
    out<<mx<<'\n';
    return 0;
}