ABC 8 D - 金塊ゲーム ( DP )

D: 金塊ゲーム - AtCoder Beginner Contest 008 | AtCoder
Let dp[ i ][ j ][ k ][ l ]: maximum score for rectangle upper left ( i, j ) lower right ( k, l )

( taken from AtCoder Beginner Contest 008 解説 )
we can split the problem into four sub problems for the four corners.
dp[ i ][ j ][ k ][ l ] = k - i + l - j + 1 + max{ dp[ i ][ j ][ mx - 1 ][ my - 1 ] + dp[ i ][ my + 1 ][ mx - 1 ][ l ] + dp[ mx + 1 ][ j ][ k ][ my - 1 ] + dp[ mx + 1 ][ my + 1 ][ k ][ l ] } Ɐ i ≤ mx ≤ k && j ≤ my ≤ l
even if it goes outside of bound i.e. when i = mx and tries to sum up [ i ][ i - 1 ] it will be alright since it's still 0.

#include <bits/stdc++.h>
using namespace std;
const int MAXW = 1e6 + 6;
const int MAXH = 1e6 + 6;
const int MAXN = 30 + 3;
typedef long long ll;
#define rep( i, a ) for(int i = 0; i < (int)( a ); ++i)

int w, h, n;
int x[ MAXN ], y[ MAXN ];

map< tuple<int, int, int, int>, ll > mtl;

ll dp(int x0, int y0, int x1, int y1){
    auto idx = make_tuple( x0, y0, x1, y1 );
    if( mtl.count( idx ) ) return mtl[ idx ];
    rep( i, n ) if( x0 <= x[ i ] && x[ i ] <= x1 && y0 <= y[ i ] && y[ i ] <= y1 ){
        mtl[ idx ] = max<ll>( mtl[ idx ], x1 - x0 + y1 - y0 + 1
                            + dp( x[ i ] + 1, y[ i ] + 1, x1, y1 )
                            + dp( x[ i ] + 1, y0, x1, y[ i ] - 1 )
                            + dp( x0, y[ i ] + 1, x[ i ] - 1, y1 )
                            + dp( x0, y0, x[ i ] - 1, y[ i ] - 1 ) );
    }
    return mtl[ idx ];
}

int main(){
    scanf("%d%d%d", &w, &h, &n);
    rep( i, n ) scanf("%d%d", &y[ i ], &x[ i ]);
    printf("%lld\n", dp( 1, 1, h, w));
    return 0;
}