Cod sursa(job #3204118)

Utilizator Sasha_12454Sasha Costea Sasha_12454 Data 15 februarie 2024 18:28:38
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in ("flip.in");
ofstream out ("flip.out");
const int NMAX=20;
int n,m;
int a[NMAX][NMAX],aux[NMAX][NMAX];
int v[NMAX];
int maxi=INT_MIN;
int solve(int poz)
{
    /*if(cnt==5)
    {
        out<<poz<<'\n';
        for(int i=1; i<=n; i++,out<<'\n')
            for(int j=1; j<=m; j++)
                out<<a[i][j]<<" ";
    }*/
    int s=0;
    for(int i=1; i<=poz; i++)
    {
        for(int j=1; j<=n; j++)
        {
            a[j][v[i]]*=-1;
        }
    }
    for(int i=1; i<=n; i++)
    {
        int sum=0;
        for(int j=1; j<=m; j++)
        {
            sum+=a[i][j];
        }
        if(sum<0)
        {
            for(int j=1; j<=m; j++)
                a[i][j]*=-1;
        }
    }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            s+=a[i][j];

    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            a[i][j]=aux[i][j];
    return s;
}
bool ok(int i)
{
    return i>=1 && i<=m;
}
void bkt(int poz)
{
    for(int i=v[poz-1]+1; i<=m; i++)
    {
        v[poz]=i;
        if(ok(poz))
        {
            maxi=max(maxi,solve(poz));
            if(ok(poz+1))
                bkt(poz+1);
        }
    }
}
int main()
{
    in>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            in>>a[i][j];
            aux[i][j]=a[i][j];
        }
    bkt(1);
    out<<maxi;
    return 0;
}