Submission #746598

#	Time	Username	Problem	Language	Result	Execution time	Memory
746598		ZeroCool	Raisins (IOI09_raisins)	C++14	100 / 100	248 ms	72056 KiB

raisins

#include <bits/stdc++.h>
#define ll long long
#define debug(x) cerr<<x<<endl

using namespace std;


const int mxn = 55;
const ll inf = 1e18;

int n,m;

ll A[mxn][mxn];
ll memo[mxn][mxn][mxn][mxn];
ll pref[mxn][mxn];




ll f(int x1,int x2,int y1,int y2){
	
	if(x1 == x2 && y1 == y2)return 0;
	if(memo[x1][x2][y1][y2] != -1)return memo[x1][x2][y1][y2];

	ll ans = inf;

	//Cut horizontally
	for(int i = x1;i<x2;i++){
		ans = min(ans, f(x1,i,y1,y2) + f(i+1,x2,y1,y2));
	}
	//Cut vetically
	for(int i = y1;i<y2;i++){
		ans = min(ans, f(x1,x2,y1,i) + f(x1,x2,i+1,y2));
	}

	return memo[x1][x2][y1][y2] = ans + (pref[x2][y2] - pref[x1-1][y2] - pref[x2][y1-1] + pref[x1-1][y1-1]);
}

void solve(int T){
	cin>>n>>m;
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=m;j++){
			cin>>A[i][j];
		}
	}
	memset(memo,-1,sizeof(memo));
	memset(pref,0,sizeof(pref));

	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=m;j++){
			pref[i][j] = pref[i-1][j] + pref[i][j-1] + A[i][j] - pref[i-1][j-1];
		}
	}
	cout<<f(1,n,1,m)<<endl;

}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int t = 1;
//	cin>>t;
	for(int i = 1;i<=t;i++)solve(i);
}

• Subtask 1: 100 / 100