TCO 2012 Round 2C 550

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <cmath>
#include <map>
#include <set>
#include <ctime>
#include <algorithm>
#include <memory.h>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<=(n); i++)
#define DFOR(i,k,n) for(int i=(k); i>=(n); i--)
#define SZ(a) (int)((a).size())
#define FA(i,v) FOR(i,0,SZ(v)-1)
#define RFA(i,v) DFOR(i,SZ(v)-1,0)
#define CLR(a) memset(a, 0, sizeof(a))
#define PB push_back
#define MP make_pair
#define LL long long
#define o_O 1000000000

int tt[210][210];
int dp[4][210][210];
int sum[4][210][210];
int dx[] = { -1, -1, 1, 1 };
int dy[] = { -1, 1, -1, 1 };

void calc( int a, int b, int i )
{
    if (dp[i][a+dx[i]][b]==-1 || dp[i][a][b+dy[i]]==-1) dp[i][a][b] = -1;
    else if (tt[a][b]>0)
    {
        if (tt[a][b] <= dp[i][a+dx[i]][b] || tt[a][b] <= dp[i][a][b+dy[i]]) dp[i][a][b] = -1;
        else dp[i][a][b] = tt[a][b];
    }
    else dp[i][a][b] = max( dp[i][a+dx[i]][b], dp[i][a][b+dy[i]] ) + 1;

    if (dp[i][a][b]==-1) sum[i][a][b] = -1;
    else sum[i][a][b] = sum[i][a+dx[i]][b] + sum[i][a][b+dy[i]] - sum[i][a+dx[i]][b+dy[i]] + dp[i][a][b];
}

struct TheMountain
{
    int minSum(int n, int m, vector <int> X, vector <int> Y, vector <int> val)
    {
        FA(a,X) tt[X[a]+1][Y[a]+1] = val[a];

        FOR(a,1,n) FOR(b,1,m) calc( a, b, 0 );
        FOR(a,1,n) DFOR(b,m,1) calc( a, b, 1 );
        DFOR(a,n,1) FOR(b,1,m) calc( a, b, 2 );
        DFOR(a,n,1) DFOR(b,m,1) calc( a, b, 3 );

        /*FOR(z,0,3)
        {
            FOR(a,1,n)
            {
                FOR(b,1,m) cerr << dp[z][a][b] << " ";
                cerr << "\n";
            }
            cerr << "\n";
        }*/

        int ans = o_O;

        FOR(a,1,n) FOR(b,1,m)
        {
            bool flag = true;
            FOR(c,0,3) if (dp[c][a][b]==-1) flag = false;
            if (flag)
            {
                int tmp = 0;
                FOR(c,0,3) tmp += sum[c][a+dx[c]][b+dy[c]];
                FOR(c,1,a-1) tmp += max( dp[0][c][b], dp[1][c][b] );
                FOR(c,a+1,n) tmp += max( dp[2][c][b], dp[3][c][b] );
                FOR(c,1,b-1) tmp += max( dp[0][a][c], dp[2][a][c] );
                FOR(c,b+1,m) tmp += max( dp[1][a][c], dp[3][a][c] );
                tmp += max( max(dp[0][a][b], dp[1][a][b]), max(dp[2][a][b], dp[3][a][b]) );
                ans = min( ans, tmp );
            }
        }

        if (ans==o_O) return -1;
        return ans;
    }
};