Submission #348657

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
348657	2021-01-15T12:59:48 Z	Farrius	Raisins (IOI09_raisins)	C++11	100 / 100	2192 ms	36332 KB

raisins

#include <bits/stdc++.h>

using namespace std;

const int MX = 55;
const int INF = INT_MAX;
int dp[MX][MX][MX][MX], pref[MX][MX], ma[MX][MX];
int n, m;

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

int fn (int x1, int y1, int x2, int y2) {
	if (dp[y1][x1][y2][x2] != INF) return dp[y1][x1][y2][x2];
	if (y1 == y2 && x1 == x2) {
		return dp[y1][x1][y2][x2] = 0;
	}
	for (int c_x = x1; c_x < x2; c_x++) {
		dp[y1][x1][y2][x2] = min(dp[y1][x1][y2][x2], fn(x1, y1, c_x, y2) + fn(c_x + 1, y1, x2, y2) + sum(x1, y1, x2, y2));
	}
	for (int c_y = y1; c_y < y2; c_y++) {
		dp[y1][x1][y2][x2] = min(dp[y1][x1][y2][x2], fn(x1, y1, x2, c_y) + fn(x1, c_y + 1, x2, y2) + sum(x1, y1, x2, y2));
	}
	return dp[y1][x1][y2][x2];
}

int main () {
	cin >> n >> m;
	for (int i = 0; i < MX; i++) {
		for (int j = 0; j < MX; j++) {
			for (int c = 0; c < MX; c++) {
				for (int k = 0; k < MX; k++) {
					dp[i][j][c][k] = INF;
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> ma[i][j];
			pref[i][j] = ma[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			pref[i][j] += pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
		}
	}
	cout << fn(1, 1, m, n) << '\n';
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	36204 KB	Output is correct
2	Correct	25 ms	36076 KB	Output is correct
3	Correct	25 ms	36076 KB	Output is correct
4	Correct	26 ms	36076 KB	Output is correct
5	Correct	25 ms	36076 KB	Output is correct
6	Correct	27 ms	36076 KB	Output is correct
7	Correct	26 ms	36204 KB	Output is correct
8	Correct	38 ms	36128 KB	Output is correct
9	Correct	49 ms	36204 KB	Output is correct
10	Correct	63 ms	36204 KB	Output is correct
11	Correct	58 ms	36204 KB	Output is correct
12	Correct	157 ms	36332 KB	Output is correct
13	Correct	256 ms	36204 KB	Output is correct
14	Correct	84 ms	36204 KB	Output is correct
15	Correct	326 ms	36204 KB	Output is correct
16	Correct	44 ms	36204 KB	Output is correct
17	Correct	130 ms	36204 KB	Output is correct
18	Correct	889 ms	36332 KB	Output is correct
19	Correct	1735 ms	36204 KB	Output is correct
20	Correct	2192 ms	36332 KB	Output is correct