Cod sursa(job #2460418)

Utilizator GabyD002Dobrita Gabriel GabyD002 Data 23 septembrie 2019 18:00:25
Problema Jocul Flip Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <bits/stdc++.h>
#define NM 20
using namespace std;
ifstream f("flip.in");
ofstream g("flip.out");

int n,m,sMax,sMaxim,sl[NM],sc[NM],a[NM][NM];
bool viz[NM],st[NM];

void Read();
void Solve();
void BKT1(int);
void BKT2(int);
void SolBKT1();
void SolBKT2();

int main()
{   Read();
    Solve();
}

void Read()
{   f>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            f>>a[i][j];
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            sl[i]+=a[i][j];
    for(int j=1; j<=m; j++)
        for(int i=1; i<=n; i++)
            sc[j]+=a[i][j];
}

void SolBKT1()
{   int sum=0;
    for(int i=1; i<=m; i++)
        sum+=(st[i] ? -sc[i] : sc[i]);
    sMax=max(sMax,sum);
}

void BKT1(int vf)
{   if(vf==m+1)
        SolBKT1();
    else
        for(int i=0; i<=1; i++)
        {   st[vf]=i;
            BKT1(vf+1);
        }
}

void SolBKT2()
{   int sum=sMax;
    for(int i=1; i<=n; i++)
        if(st[i])
            sum+=-2*sl[i];
    sMaxim=max(sMaxim,sum);
}

void BKT2(int vf)
{   if(vf==n+1)
        SolBKT2();
    else
        for(int i=0; i<=1; i++)
        {   st[vf]=i;
            BKT2(vf+1);
        }
}

void Solve()
{   BKT1(1);
    for(int i=1; i<=n; i++)
        st[i]=false;
    BKT2(1);
    g<<sMaxim;
}