제출 #1133722

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1133722		yellowtoad	Raisins (IOI09_raisins)	C++20	100 / 100	442 ms	24772 KiB

raisins

#include <iostream>
using namespace std;

int n, m,dp[60][60][60][60], ps[60][60];

int solve(int x1, int y1, int x2, int y2) {
	if ((x1 == x2) && (y1 == y2)) return 0;
	if (dp[x1][y1][x2][y2]) return dp[x1][y1][x2][y2];
	int minn = 1e9;
	for (int i = x1; i < x2; i++) minn = min(minn,solve(x1,y1,i,y2)+solve(i+1,y1,x2,y2));
	for (int i = y1; i < y2; i++) minn = min(minn,solve(x1,y1,x2,i)+solve(x1,i+1,x2,y2));
	return (dp[x1][y1][x2][y2] = minn+ps[x2][y2]-ps[x1-1][y2]-ps[x2][y1-1]+ps[x1-1][y1-1]);
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> ps[i][j];
			ps[i][j] += ps[i][j-1]+ps[i-1][j]-ps[i-1][j-1];
		}
	}
	cout << solve(1,1,n,m) << endl;
}

• Subtask 1: 100 / 100