Submission #585646

#	Time	Username	Problem	Language	Result	Execution time	Memory
585646		Drew_	Raisins (IOI09_raisins)	C++17	100 / 100	752 ms	27236 KiB

raisins

#include <bits/stdc++.h>
using namespace std;

const int MAX = 69;
const int inf = 1e9 + 69;

int N, M;
int pfx[MAX][MAX];
int dp[MAX][MAX][MAX][MAX];

inline int sum(int r1, int c1, int r2, int c2)
{
	return pfx[r2][c2] - pfx[r1-1][c2] - pfx[r2][c1-1] + pfx[r1-1][c1-1];
}

inline int solve(int r1, int c1, int r2, int c2)
{
	if (r1 == r2 && c1 == c2)
		return 0;
	if (dp[r1][c1][r2][c2] != inf)
		return dp[r1][c1][r2][c2];

	for (int i = r1; i < r2; ++i)
		dp[r1][c1][r2][c2] = min(dp[r1][c1][r2][c2], sum(r1, c1, r2, c2) + solve(r1, c1, i, c2) + solve(i+1, c1, r2, c2));
	for (int i = c1; i < c2; ++i)
		dp[r1][c1][r2][c2] = min(dp[r1][c1][r2][c2], sum(r1, c1, r2, c2) + solve(r1, c1, r2, i) + solve(r1, i+1, r2, c2));
	return dp[r1][c1][r2][c2];
}

int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> M;
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= M; ++j)
			cin >> pfx[i][j], pfx[i][j] += pfx[i-1][j] + pfx[i][j-1] - pfx[i-1][j-1];

	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= M; ++j)
			for (int k = i; k <= N; ++k)
				for (int l = j; l <= M; ++l)
					dp[i][j][k][l] = inf;

	cout << solve(1, 1, N, M) << '\n';
	return 0;
}

• Subtask 1: 100 / 100