Submission #348656

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
348656	2021-01-15T12:58:45 Z	Farrius	Raisins (IOI09_raisins)	C++11	0 / 100	2175 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 << pref[i][j] << ' ';
		}
		cout << '\n';
	}
	cout << fn(1, 1, m, n) << '\n';
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	27 ms	36076 KB	Output isn't correct
2	Incorrect	26 ms	36076 KB	Output isn't correct
3	Incorrect	26 ms	36076 KB	Output isn't correct
4	Incorrect	26 ms	36076 KB	Output isn't correct
5	Incorrect	27 ms	36224 KB	Output isn't correct
6	Incorrect	26 ms	36076 KB	Output isn't correct
7	Incorrect	26 ms	36204 KB	Output isn't correct
8	Incorrect	40 ms	36120 KB	Output isn't correct
9	Incorrect	52 ms	36204 KB	Output isn't correct
10	Incorrect	64 ms	36204 KB	Output isn't correct
11	Incorrect	58 ms	36204 KB	Output isn't correct
12	Incorrect	157 ms	36332 KB	Output isn't correct
13	Incorrect	262 ms	36204 KB	Output isn't correct
14	Incorrect	82 ms	36204 KB	Output isn't correct
15	Incorrect	323 ms	36204 KB	Output isn't correct
16	Incorrect	44 ms	36096 KB	Output isn't correct
17	Incorrect	126 ms	36332 KB	Output isn't correct
18	Incorrect	910 ms	36332 KB	Output isn't correct
19	Incorrect	1902 ms	36268 KB	Output isn't correct
20	Incorrect	2175 ms	36268 KB	Output isn't correct