제출 #621434

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
621434		as111	Raisins (IOI09_raisins)	C++14	45 / 100	244 ms	26800 KiB

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 / 100