Submission #520185

#	Time	Username	Problem	Language	Result	Execution time	Memory
520185		tkwiatkowski	Raisins (IOI09_raisins)	C++17	100 / 100	247 ms	32244 KiB

raisins

/*
	Zadanie: Raisins
	Autor: Tomasz Kwiatkowski
*/

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back

using namespace std;
typedef long long ll;

const int MAXN = 57;

int pref[MAXN][MAXN];
int dp[MAXN][MAXN][MAXN][MAXN];

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

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);

	int n, m;
	cin >> n >> m;
	for (int x1 = 1; x1 <= n; ++x1)
		for (int y1 = 1; y1 <= m; ++y1)
			for (int x2 = 1; x2 <= n; ++x2)
				for (int y2 = 1; y2 <= m; ++y2)
					dp[x1][y1][x2][y2] = 1e9;

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			int a;
			cin >> a;
			dp[i][j][i][j] = 0;
			pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + a;
		}
	}

	for (int x2 = 1; x2 <= n; ++x2) {
		for (int y2 = 1; y2 <= m; ++y2) {
			for (int x1 = x2; x1 >= 1; --x1) {
				for (int y1 = y2; y1 >= 1; --y1) {
					for (int k = x1; k < x2; ++k)
						dp[x1][y1][x2][y2] = min(dp[x1][y1][k][y2] + dp[k + 1][y1][x2][y2] + sum(x1, y1, x2, y2), dp[x1][y1][x2][y2]);
					for (int k = y1; k < y2; ++k)
						dp[x1][y1][x2][y2] = min(dp[x1][y1][x2][k] + dp[x1][k + 1][x2][y2] + sum(x1, y1, x2, y2), dp[x1][y1][x2][y2]);
					//printf("(%d, %d), (%d, %d) %d\n", x1, y1, x2, y2, dp[x1][y1][x2][y2]);
				}
			}
		}
	}
	cout << dp[1][1][n][m] << '\n';
	return 0;
}

• Subtask 1: 100 / 100