Submission #366749

#	Time	Username	Problem	Language	Result	Execution time	Memory
366749		kostia244	Raisins (IOI09_raisins)	C++17	100 / 100	1056 ms	36332 KiB

raisins

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
const int maxn = 55;
int n, m, a[maxn][maxn], p[maxn][maxn];
int dp[maxn][maxn][maxn][maxn];
int f(int xl, int xr, int yl, int yr) {
	int &ans = dp[xl][xr][yl][yr];
	if(ans >= 0) return ans;
	if(xl == xr && yl == yr) return 0;
	ans = 1<<30;
	for(int c = xl; c < xr; c++) ans = min(ans, f(xl, c, yl, yr) + f(c+1, xr, yl, yr));
	for(int c = yl; c < yr; c++) ans = min(ans, f(xl, xr, yl, c) + f(xl, xr, c+1, yr));
	--xl,--yl;ans += p[xr][yr] - p[xl][yr] - p[xr][yl] + p[xl][yl];
	return ans;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			cin >> a[i][j], p[i][j] = a[i][j] + p[i-1][j];
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			p[i][j] += p[i][j-1];
	memset(dp, -1, sizeof dp);
	cout << f(1, n, 1, m);
} 

• Subtask 1: 100 / 100