Submission #308762

#	Time	Username	Problem	Language	Result	Execution time	Memory
308762		Temmie	Raisins (IOI09_raisins)	C++17	100 / 100	1503 ms	44280 KiB

raisins

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