oj.uz

답안 #621434

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
621434 2022-08-03T19:07:13 Z as111 건포도 (IOI09_raisins) C++14
45 / 100
 244 ms 26800 KB 
#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

# 결과 실행 시간 메모리 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