Submission #621434

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
621434	2022-08-03T19:07:13 Z	as111	Raisins (IOI09_raisins)	C++14	45 / 100	244 ms	26800 KB

raisins

#include <iostream>

#define MAXN 50

using namespace std;
int dp[MAXN + 1][MAXN + 1][MAXN + 1][MAXN + 1]; // minimum cost to cut ijkl rectangle
int numr[MAXN + 1][MAXN + 1];
int main() {
	int N, M;
	cin >> N >> M;
	for (int i = 0; i <= MAXN; i++) {
		for (int j = 0; j <= MAXN; j++) {
			for (int k = 0; k <= MAXN; k++) {
				fill(dp[i][j][k], dp[i][j][k] + MAXN + 1, 2500001);
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> numr[i][j];
			dp[i][i][j][j] = 0; // base case 1x1 rect
			numr[i][j] += numr[i][j - 1] + numr[i - 1][j] - numr[i - 1][j - 1];
		}
	}
	for (int ln = 0; ln < N; ln++) { // length on n side
		for (int lm = 0; lm < M; lm++) {
			for (int i = 1; i <= N; i++) {
				if (i + ln > N) break;
				for (int k = 1; k <= M; k++) {
					if (k + lm > M) break;
					int j = i + ln;
					int l = k + lm;
					int total = numr[j][l] - numr[j][k - 1] - numr[i - 1][l] + numr[i - 1][k - 1]; // total raisins in rect
					for (int d = i; d < j; d++) { // divide along n side first
						dp[i][j][k][l] = min(dp[i][j][k][l], total + dp[i][d][k][l] + dp[d+1][j][k][l]);
					}
					for (int d = k; d < l; d++) { // divide
						dp[i][j][k][l] = min(dp[i][j][k][l], total + dp[i][j][k][d] + dp[i][j][d+1][l]);
					}
				}
			}
		}
	}
	cout << dp[1][N][1][M]; // ans is entire rectangle
}

Subtask #1

45.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	26680 KB	Output is correct
2	Correct	19 ms	26708 KB	Output is correct
3	Correct	20 ms	26700 KB	Output is correct
4	Correct	20 ms	26768 KB	Output is correct
5	Correct	19 ms	26680 KB	Output is correct
6	Correct	19 ms	26760 KB	Output is correct
7	Correct	19 ms	26680 KB	Output is correct
8	Correct	20 ms	26708 KB	Output is correct
9	Incorrect	23 ms	26672 KB	Output isn't correct
10	Incorrect	23 ms	26756 KB	Output isn't correct
11	Incorrect	20 ms	26680 KB	Output isn't correct
12	Incorrect	40 ms	26772 KB	Output isn't correct
13	Incorrect	48 ms	26776 KB	Output isn't correct
14	Correct	26 ms	26756 KB	Output is correct
15	Incorrect	59 ms	26768 KB	Output isn't correct
16	Incorrect	25 ms	26800 KB	Output isn't correct
17	Incorrect	40 ms	26772 KB	Output isn't correct
18	Incorrect	148 ms	26716 KB	Output isn't correct
19	Incorrect	217 ms	26780 KB	Output isn't correct
20	Incorrect	244 ms	26776 KB	Output isn't correct