Submission #927942

#	Time	Username	Problem	Language	Result	Execution time	Memory
927942		TAhmed33	Raisins (IOI09_raisins)	C++98	100 / 100	516 ms	26968 KiB

raisins

#include <bits/stdc++.h>
using namespace std;
int n, m;
int arr[51][51] = {};
int pref(int a, int b, int c, int d) {
	return arr[c][d] - arr[a - 1][d] - arr[c][b - 1] + arr[a - 1][b - 1];
}
int dp[51][51][51][51];
int ans (int a, int b, int c, int d) {
	int &ret = dp[a][b][c][d];
	if (ret != -1) return ret;
	if (a == c && b == d ) return ret = 0;
	int mx = 1e9;
	for (int i = 1; i <= d - b; i++) {
		mx = min(mx, ans(a, b, c, b + i - 1) + ans(a, b + i, c, d));
	}
	for (int i = 1; i <= c - a; i++) {
		mx = min(mx, ans(a, b, a + i - 1, d) + ans(a + i, b, c, d));
	}
	return ret = mx + pref(a, b, c, d);
}
int main () {
	memset(arr, 0, sizeof(arr));
	memset(dp, -1, sizeof(dp));
	cin >> n >> m;
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> arr[i][j];

	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) arr[i][j] += arr[i][j - 1];
	for (int j = 1; j <= m; j++) for (int i = 1; i <= n; i++) arr[i][j] += arr[i - 1][j];

	cout << ans(1, 1, n, m);
}

• Subtask 1: 100 / 100