Cod sursa(job #2166725)

Utilizator ianic1999Ianic Umanschii ianic1999 Data 13 martie 2018 18:37:48
Problema Jocul Flip Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("flip.in");
ofstream fout("flip.out");
int t[17][17];
int n,m,i,j,k;
long long s,smax;
int a[17],b[17];
struct abc{
int s;
int nr;
};

void check(string q, string p)
{
    long long s=0;
    int aa[17];
    int bb[17];
    int i,j;
    for(i=1;i<=n;i++) aa[i]=a[i];
    for(j=1;j<=m;j++) bb[i]=b[i];

    for(i=0;i<n;i++)
        if(q[i]=='1')
    {
        aa[i+1]*=-1;
        for(j=1;j<=m;j++)
            bb[j]-=2*t[i+1][j];
    }

    for(i=0;i<m;i++)
        if(p[i]=='1')
    {
        bb[i+1]*=-1;
        for(j=1;j<=n;j++)
            aa[j]-=2*t[j][i+1];
    }
    for(i=1;i<=n;i++) s+=aa[i];
    smax=max(s,smax);
}

void gen2(string s, string x)
{
    if(x.length()==m) check(s,x);
    else
    {
        if(b[x.length()+1]>0) gen2(s,x+'0');
        else
        {
            gen2(s,x+'0');
            gen2(s,x+'1');
        }
    }
}

void gen1(string s)
{
    if(s.length()==n) gen2(s,"");
    else
    {
        if(a[s.length()+1]>0) gen1(s+'0');
        else
        {
            gen1(s+'0');
            gen1(s+'1');
        }
    }
}


int main(){
fin>>n>>m;
s=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
    fin>>t[i][j];
    s+=t[i][j];
}
smax=s;

for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
     a[i]+=t[i][j];
for(j=1;j<=m;j++)
    for(i=1;i<=n;i++)
     b[j]+=t[i][j];

gen1("");
fout<<smax;
return 0;
}