Cod sursa(job #2081443)

Utilizator AndreiStanescuAlloys Nokito AndreiStanescu Data 4 decembrie 2017 18:38:14
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 kb
/*#include<bits/stdc++.h>
#define N 97
#define M 322
using namespace std;
bool viz[N];
int n,m,j,Sol,Cos[N],tel[N];
typedef struct config{int x, y;};
config G[M];
void read()
{
    freopen("rmvc.in","r",stdin);
    scanf("%d%d\n",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&G[i].x,&G[i].y);
}

void backtr(int k, int j)
{
    if(k>Sol) return ;
    bool ok=0;
    int i,lm;
    for(i=j+1;i<=m && !ok;i++)
       {
           if(viz[G[i].x] || viz[G[i].y] ) continue;
           ok=1;
           viz[G[i].x]=1;
           //pastrez solutia
           Cos[k+1]=G[i].x;
           backtr(k+1,i);
           viz[G[i].x]=0;
           viz[G[i].y]=1;
           Cos[k+1]=G[i].y;
           backtr(k+1,i);
           viz[G[i].y]=0;
       }
    if(!ok)
    {
        Sol=k;
        for(lm=1;lm<=k;lm++)
            tel[lm]=Cos[lm];
    }

}


int main()
{
    read();
    Sol=18;
    //backtr(0,0);
    backtr(0,0);
    freopen("rmvc.out","w",stdout);
    cout<<Sol<<'\n';
    for(int i=1;i<=Sol;i++)
        cout<<tel[i]<<' ';
}*/


/*....................*/

#include<bits/stdc++.h>
using namespace std;
int a[20][20];
int n, m;
int semn[22];
long long Dim=-16000000001;

void read()
{
    ifstream fin("flip.in");
    fin>>n>>m;
    int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        fin>>a[i][j];
    fin.close();
}

long long suma()
{   long long ans=0;
    for(int i=1;i<=n;i++)
    {
        long long in=0;
        for(int j=1;j<=m;j++)
        {
            if(!semn[j]) in+=a[i][j];
            else in-=a[i][j];
        }
        //tin cont ca linia schimbata cu -1 e independenta de suma finala
        if(in>(-in)) ans+=in;
        else ans-=in;
    }
    return ans;
}


void backtr(int k)
{
    if(k==m+1)
    {
        long long sol;
        sol=suma();
        if(sol>Dim) Dim=sol;
        return ;
    }
    semn[k]=0;
    backtr(k+1);
    semn[k]=1;
    backtr(k+1);
}


int main()
{
    read();
    backtr(1);
    ofstream fout("flip.out");
    fout<<Dim;
    fout.close();

}