Submission #1188725

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188725		peteza	Raisins (IOI09_raisins)	C++20	100 / 100	411 ms	53596 KiB

raisins

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, m;
ll dp[51][51][51][51];
ll sc[51][51];

ll getqs(int i1, int j1, int i2, int j2) {
	return sc[i2][j2] - sc[i1-1][j2] - sc[i2][j1-1] + sc[i1-1][j1-1];
}

ll rec(int i1, int j1, int i2, int j2) {
	ll &cdp = dp[i1][j1][i2][j2];
	if(~cdp) return cdp;
	cdp = LLONG_MAX;
	ll cqs = getqs(i1,j1,i2,j2);
	for(int ik=i1;ik<i2;ik++)
		cdp = min(cdp, cqs+rec(i1,j1,ik,j2)+rec(ik+1,j1,i2,j2));
	for(int jk=j1;jk<j2;jk++)
		cdp = min(cdp, cqs+rec(i1,j1,i2,jk)+rec(i1,jk+1,i2,j2));
	return cdp;
}

int main() {
	// your code goes here
	cin >> n >> m;
	for(int i=1;i<=n;i++ ) {
		for(int j=1;j<=m;j++) {
			cin >> sc[i][j];
			sc[i][j] = sc[i][j] + sc[i-1][j] + sc[i][j-1] - sc[i-1][j-1];
		}
	}
	memset(dp, -1, sizeof dp);
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) dp[i][j][i][j]=0;
	cout << rec(1,1,n,m);
	return 0;
}

• Subtask 1: 100 / 100