Submission #312224

#	Time	Username	Problem	Language	Result	Execution time	Memory
312224		joseacaz	Raisins (IOI09_raisins)	C++17	100 / 100	870 ms	22904 KiB

raisins

#include <iostream>
#define MAXN 55

using namespace std;
typedef long long int lld;

int N, M, choc[MAXN][MAXN], pre[MAXN][MAXN], DP[MAXN][MAXN][MAXN][MAXN];

int sum ( int x1, int y1, int x2, int y2 )
{
	return pre[x2][y2] - pre[x1 - 1][y2] - pre[x2][y1 - 1] + pre[x1 - 1][y1 - 1];
}

int dp ( int x1, int y1, int x2, int y2 )
{
	if ( x1 == x2 && y1 == y2 )
		return 0;
	
	if ( DP[x1][y1][x2][y2] )
		return DP[x1][y1][x2][y2];
	
	int aux = (1 << 30);
	if ( x1 < x2 )
		for ( int i = x1; i < x2; i++ )
			aux = min ( aux, dp ( x1, y1, i, y2 ) + dp ( i + 1, y1, x2, y2 ) );

	if ( y1 < y2 )
		for ( int i = y1; i < y2; i++ )
			aux = min ( aux, dp ( x1, y1, x2, i ) + dp ( x1, i + 1, x2, y2 ) );

	DP[x1][y1][x2][y2] = aux + sum ( x1, y1, x2, y2 );

	//cout << "returning " << DP[x1][y1][x2][y2] << " for " << x1 << " " << y1 << " " << x2 << " " << y2 << "\n";
	return DP[x1][y1][x2][y2];
}

int main ()
{
	cin >> N >> M;
	for ( int i = 1; i <= N; i++ )
	{
		for ( int j = 1; j <= M; j++ )
		{
			cin >> choc[i][j];
			pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + choc[i][j];
		}
	}

	cout << dp ( 1, 1, N, M ) << "\n";
	return 0;
}

• Subtask 1: 100 / 100