oj.uz

답안 #348656

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
348656 2021-01-15T12:58:45 Z Farrius 건포도 (IOI09_raisins) C++11
0 / 100
 2175 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 << pref[i][j] << ' ';
		}
		cout << '\n';
	}
	cout << fn(1, 1, m, n) << '\n';
}

Subtask #1
0 / 100.0

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