Submission #157847

---

Source Code Expand

#include <bits/stdc++.h>

#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define lli long long int
#define all( gg )	gg.begin(),gg.end()
#define foreach( gg,itit )	for( typeof(gg.begin()) itit=gg.begin();itit!=gg.end();itit++ )
#define FP( ii,aa,bb ) for( int ii=aa;ii<=bb;ii++ )
#define FM( ii,aa,bb ) for( int ii=aa;ii>=bb;ii-- )

using namespace std;

int m,n,t,h[700][700],dp[700][700];

int main(){
	cin >> m >> n >> t;
	int x,y;
	while( t-- ){
		cin >> x >> y;
		h[x][y] = 1;
	}
	FP( a,1,m )
		FP( b,1,n ){
			dp[a][b] = a*b;
			if( h[a][b] ){
				dp[a][b] = 0;
				continue;
			}
			FP( i,1,a-1 )	dp[a][b] = min( dp[a][b],dp[i][b]+dp[a-i][b] );
			FP( i,1,b-1 )	dp[a][b] = min( dp[a][b],dp[a][i]+dp[a][b-i] );
		}
	cout << dp[m][n] << endl;
}

Submission Info

Judge Result