oj.uz

답안 #308762

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
308762 2020-10-01T21:23:28 Z Temmie 건포도 (IOI09_raisins) C++17
100 / 100
 1503 ms 44280 KB 
#include <bits/stdc++.h>

int n, m;
std::vector <std::vector <int>> g;
std::vector <std::vector <std::vector <std::vector <int>>>> dp(55, std::vector <std::vector <std::vector <int>>> (55, std::vector <std::vector <int>> (55, std::vector <int> (55, 0))));

int f(int x, int xx, int y, int yy) {
	if (x == xx - 1 && y == yy - 1) return 0;
	if (dp[x][xx][y][yy]) return dp[x][xx][y][yy];
	int r = 1 << 30;
	for (int i = x + 1; i < xx; i++)
		r = std::min(r, f(x, i, y, yy) + f(i, xx, y, yy));
	for (int i = y + 1; i < yy; i++)
		r = std::min(r, f(x, xx, i, yy) + f(x, xx, y, i));
	dp[x][xx][y][yy] = r + g[xx][yy] + g[x][y] - g[x][yy] - g[xx][y];
	return dp[x][xx][y][yy];
}

int main() {
	std::ios::sync_with_stdio(0); std::cin.tie(0);
	
	std::cin >> n >> m;
	g.resize(n + 1, std::vector <int> (m + 1));
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			std::cin >> g[i][j];
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			g[i][j] += g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1];
	int ans = f(0, n, 0, m);
	std::cout << ans << "\n";
	
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 44152 KB Output is correct
2 Correct 37 ms 44160 KB Output is correct
3 Correct 36 ms 44152 KB Output is correct
4 Correct 38 ms 44152 KB Output is correct
5 Correct 38 ms 44160 KB Output is correct
6 Correct 36 ms 44152 KB Output is correct
7 Correct 37 ms 44152 KB Output is correct
8 Correct 50 ms 44160 KB Output is correct
9 Correct 61 ms 44160 KB Output is correct
10 Correct 74 ms 44160 KB Output is correct
11 Correct 66 ms 44160 KB Output is correct
12 Correct 168 ms 44152 KB Output is correct
13 Correct 264 ms 44280 KB Output is correct
14 Correct 88 ms 44152 KB Output is correct
15 Correct 316 ms 44160 KB Output is correct
16 Correct 60 ms 44152 KB Output is correct
17 Correct 155 ms 44160 KB Output is correct
18 Correct 804 ms 44280 KB Output is correct
19 Correct 1277 ms 44280 KB Output is correct
20 Correct 1503 ms 44240 KB Output is correct