oj.uz

Submission #927942

# Submission time Handle Problem Language Result Execution time Memory
927942 2024-02-15T14:26:43 Z TAhmed33 Raisins (IOI09_raisins) C++
100 / 100
 516 ms 26968 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26716 KB Output is correct
2 Correct 4 ms 26712 KB Output is correct
3 Correct 4 ms 26716 KB Output is correct
4 Correct 4 ms 26768 KB Output is correct
5 Correct 4 ms 26968 KB Output is correct
6 Correct 4 ms 26716 KB Output is correct
7 Correct 4 ms 26712 KB Output is correct
8 Correct 10 ms 26920 KB Output is correct
9 Correct 14 ms 26716 KB Output is correct
10 Correct 19 ms 26716 KB Output is correct
11 Correct 17 ms 26744 KB Output is correct
12 Correct 69 ms 26964 KB Output is correct
13 Correct 93 ms 26964 KB Output is correct
14 Correct 26 ms 26716 KB Output is correct
15 Correct 105 ms 26904 KB Output is correct
16 Correct 15 ms 26712 KB Output is correct
17 Correct 42 ms 26716 KB Output is correct
18 Correct 262 ms 26912 KB Output is correct
19 Correct 425 ms 26716 KB Output is correct
20 Correct 516 ms 26912 KB Output is correct