Cod sursa(job #2577372)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 9 martie 2020 09:44:50
Problema Jocul Flip Scor 10
Compilator cpp-64 Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul II Marime 0.96 kb
#include <bits/stdc++.h>
#define Dim 17
using namespace std;
ifstream f("flip.in");
ofstream g("flip.out");
typedef long long ll;

ll N,M,dp[Dim][Dim],C[Dim],R[Dim],A[Dim][Dim],ans,s;

void BKT(int i,int j)
{
    if(i!=0||j!=0)
    {
        dp[i][j]=max(dp[i][j],max(dp[i-1][j]-2*R[i],dp[i-1][j]));
        dp[i][j]=max(dp[i][j],max(dp[i][j-1],dp[i][j-1]-2*C[j]));
        dp[i][j]=max(dp[i][j],max(dp[i-1][j-1],dp[i-1][j-1]-2*(C[j]+R[i])));
    }
    ans=max(ans,dp[i][j]);


    for(int line=i+1;line<=N;line++)
    {
        BKT(line,j);
    }
    for(int col=j+1;col<=M;col++)
    {
        BKT(i,col);
    }
}

int main()
{
    f>>N>>M;
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=M;j++)
        {
            f>>A[i][j];
            s+=A[i][j];
            R[i]=R[i]+A[i][j];
            C[j]+=A[i][j];
            dp[i][j]=INT_MIN;
        }
    }
    dp[0][0]=s;
    ans=s;
    BKT(0,0);
    g<<ans;

    return 0;
}