Cod sursa(job #2639863)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 4 august 2020 12:46:47
Problema Jocul Flip Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("flip.in");
ofstream g("flip.out");
typedef long long ll;
const int dim=(1<<17);
const ll inf=-2e9;
ll n,m,ans0,ans1,S;

int main()
{
    f>>n>>m;
    vector < ll > sum(m,0),sum1(n,0);
    vector < vector < ll > > v(n,vector < ll > (m));
    vector < vector < ll >  > dp(2, vector < ll > (dim,inf));
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            f>>v[i][j];
            S+=v[i][j];
            sum[j]+=v[i][j];
            sum1[i]+=v[i][j];
        }

    dp[0][0]=0;
    for(int j=0;j<m;j++) dp[0][0]+=sum[j];

    ans0=S;
    for(int i=1;i<(1<<m);i++)
    {
        for(int j=0;(1<<j)<=i;j++)
        if( ( i & (1<<j) ) > 0 )
        {
            dp[0][i]=max(dp[0][i],dp[0][i^(1<<j)]-2*sum[j]);
        }
        ans0=max(ans0,dp[0][i]);
    }


    dp[1][0]=0;
    for(int i=0;i<n;i++) dp[1][0]+=sum1[i];

    ans1=S;
    for(int i=1;i<(1<<n);i++)
    {
        for(int j=0;(1<<j)<=i;j++)
        if( ( i & (1<<j) ) > 0 )
        {
            dp[1][i]=max(dp[1][i],dp[1][i^(1<<j)]-2*sum1[j]);
        }
        ans1=max(ans1,dp[1][i]);
    }

    g<<ans0+ans1-S;

    return 0;
}