Cod sursa(job #2038630)

Utilizator TheOlarOlar Alexandru TheOlar Data 13 octombrie 2017 21:08:29
Problema Jocul Flip Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <iostream>
#include <fstream>
#include <climits>

using namespace std;

int n,m,a[18][18];
bool semn[18];
long long smaxi=INT_MIN;

ifstream fin("flip.in");
ofstream fout("flip.out");
long long int sol()
{
    long long int smaxi=0,sum=0;
    for(int i=1;i<=n;i++)
    {
        sum=0;
        for(int j=1;j<=m;j++)
            if(semn[j])
               sum=a[i][j]+sum;
            else
               sum=sum-a[i][j];
        if(sum<0)
            smaxi=smaxi-sum;
        else
            smaxi=smaxi+sum;
    }
    return smaxi;
}
void backtracking(int k)
{
    if(k<=n+1)
    {

    if(k>m)
    {
        int sum=sol();
        if(sum>smaxi)
            smaxi=sum;
        return ;
    }
    semn[k]=false;
    backtracking(k+1);
    semn[k]=true;
    backtracking(k+1);
    }
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
          fin>>a[i][j];
    backtracking(1);
    fout<<smaxi;
}