Cod sursa(job #3278362)

Utilizator Radu_Stefan2010Radu Loga Radu_Stefan2010 Data 19 februarie 2025 15:54:12
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("flip.in");
ofstream out("flip.out");

int n,m,l[20],c[20],st[20],sc[20],b[20][20],a[20][20],smax,x;

void verif()//O(n*m)
{
    int suma=0;
//    for(int i=1;i<=n;i++)
//        for(int j=1;j<=m;j++)
//            b[i][j]=a[i][j];
//    for(int j=1;j<=m;j++)
//        sc[j]=c[j];
//    for(int i=1; i<=n; i++)
//    {
//        if(!st[i])
////            suma+=l[i];
////        else
////            suma+=(l[i]*(-1));
//        if(st[i])
//        {
//            for(int j=1; j<=m; j++)
//            {
//                sc[j]+=2*(-1*a[i][j]);
//                b[i][j]=-b[i][j];
//            }
//
//        }
//    }
    for(int j=1; j<=m; j++)
    {
        if(sc[j]<0)
            suma+=abs(sc[j]);
        else
            suma+=sc[j];
    }
    if(suma>smax)
        smax=suma;
}
void back(int k)//O(2^n*verif)
{
    if(k>n)
        verif();
    else
    {
        for(int i=0; i<=1; i++) ///0 nu fac nimic la 1 inm cu -1
        {
            st[k]=i;
            if(i==1)
            {
                for(int j=1;j<=m;j++)
                    b[k][j]=-1*a[k][j],sc[j]+=(-2*a[k][j]);
            }
            back(k+1);
            if(i==1)
                for(int j=1;j<=m;j++)
                    b[k][j]=b[k][j]*(-1),sc[j]+=2*a[k][j];
        }
    }
}
int main()//O(back)
{
    in>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            in>>a[i][j];
            l[i]+=a[i][j];
            c[j]+=a[i][j];
            b[i][j]=a[i][j];
            sc[j]=c[j];
        }
    smax=0;
    back(2);
    out<<smax;
    return 0;
}