oj.uz

답안 #348657

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
348657 2021-01-15T12:59:48 Z Farrius 건포도 (IOI09_raisins) C++11
100 / 100
 2192 ms 36332 KB 
#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

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