Cod sursa(job #1323337)

Utilizator laurionLaurentiu Ion laurion Data 20 ianuarie 2015 22:30:26
Problema Jocul Flip Scor 70
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul II Marime 1.98 kb
#include<fstream>
#include<cstdio>
#include<climits>
#include <cstring>
//int a[20][20]/*,b[20][20]*/,s,max=INT_MIN,i;
/*
void back_l(int k)
{
    if(k==n)
    {
        s=0;
        for(int i=0;i<n;++i)
            for(int j=0;j<m;++j)
                s+=a[i][j];
        if(max<s)
            max=s;
        return;
    }
    for(i=k;i<n;++i)
    {
        back_l(i+1);
        //back_c(0);
        for(int j=0;j<m;++j)
            a[i][j]=-a[i][j];
        back_l(i+1);
        //back_c(0);
        for(int j=0;j<m;++j)
            a[i][j]=-a[i][j];
    }
}
*/
int main()
{
    int a[20][20]={0}/*,b[20][20]*/,s,max=INT_MIN,i;

    std::ifstream fin("flip.in");
    std::ofstream fout("flip.out");
     int n,m;
     fin>>n>>m;
     for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
            fin>>a[i][j];
    //int b[20][20];
    //memcpy(b,a,sizeof(a));
    //back_l(0);
    int n2=1<<n;
    int m2=1<<m;
    int j,y,t;
    int sn,sp;
    for(int x=0;x<n2;++x)
    {
        s=0;
        for(i=0;i<n;++i)
        {
            if(x&(1<<i))
            {
                for(j=0;j<m;++j)
                    a[i][j]=-a[i][j];
            }

        }

        for(j=0;j<m;++j)
        {
            sn=sp=0;
            for(i=0;i<n;++i)
            {
                if(a[i][j]<0)
                    sn+=-a[i][j];
                else
                    sp+=a[i][j];
            }
            if(sn>sp)
                for(i=0;i<n;++i)
                {
                    s-=a[i][j];
                }
            else
                for(i=0;i<n;++i)
                {
                    s+=a[i][j];
                }

        }
//        s=0;
//        for(i=0;i<n;++i)
//            for(j=0;j<m;++j)
//                s+=a[i][j];
        if(s>max)
            max=s;
       for(i=0;i<n;++i)
        {
            if(x&(1<<i))
            {
                for(j=0;j<m;++j)
                    a[i][j]=-a[i][j];
            }
        }

       //memcpy(a,b,sizeof(b));
    }
    fout<<max<<'\n';


    return 0;
}