Submission #384991

#	Time	Username	Problem	Language	Result	Execution time	Memory
384991		ritul_kr_singh	Raisins (IOI09_raisins)	C++17	100 / 100	749 ms	49260 KiB

raisins

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'

int n, m;
int g[50][50], dp[50][50][50][50];

int calc(int xa, int ya, int xb, int yb){
	if(xa==xb and ya==yb) return dp[xa][ya][xb][yb] = 0;
	if(dp[xa][ya][xb][yb]!=-1) return dp[xa][ya][xb][yb];

	int sum = g[xb][yb];
	if(xa) sum -= g[xa-1][yb];
	if(ya) sum -= g[xb][ya-1];
	if(xa and ya) sum += g[xa-1][ya-1];

	int res = 1e18;

	for(int i=xa; i<xb; ++i)
		res = min(res, calc(xa, ya, i, yb) + calc(i+1, ya, xb, yb));
	for(int i=ya; i<yb; ++i)
		res = min(res, calc(xa, ya, xb, i) + calc(xa, i+1, xb, yb));
	return dp[xa][ya][xb][yb] = res + sum;
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	for(int i=0; i<n; ++i){
		for(int j=0; j<m; ++j){
			cin >> g[i][j];
			if(i) g[i][j] += g[i-1][j];
			if(j) g[i][j] += g[i][j-1];
			if(i and j) g[i][j] -= g[i-1][j-1];
			for(int k=0; k<n; ++k)
				for(int l=0; l<m; ++l)
					dp[i][j][k][l] = -1;
		}
	}

	cout << calc(0, 0, n-1, m-1);
}

• Subtask 1: 100 / 100