Submission #211245

#	Time	Username	Problem	Language	Result	Execution time	Memory
211245		socho	Raisins (IOI09_raisins)	C++14	100 / 100	1072 ms	36344 KiB

raisins

#include "bits/stdc++.h"
using namespace std;
// #define endl '\n'
// #define int long long

const int MXN = 55, MXM = 55;
int n, m;
int arr[MXN][MXM];

int dp[MXN][MXN][MXM][MXM];

int solve(int t, int d, int l, int r) {
	if (t == d && l == r) return 0;
	if (dp[t][d][l][r] != -1) return dp[t][d][l][r];
	int sm = 0;
	for (int i=t; i<=d; i++) {
		for (int j=l; j<=r; j++) {
			sm += arr[i][j];
		}
	}
	int mx = INT_MAX;
	for (int i=t; i<d; i++) {
		mx = min(mx, solve(t, i, l, r) + solve(i+1, d, l, r));
	}
	for (int i=l; i<r; i++) {
		mx = min(mx, solve(t, d, l, i) + solve(t, d, i+1, r));
	}
	return dp[t][d][l][r] = sm + mx;
}

signed main() {
	
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	memset(dp, -1, sizeof dp);
	
	cin >> n >> m;
	for (int i=0; i<n; i++) {
		for (int j=0; j<m; j++) {
			cin >> arr[i][j];
		}
	}
	cout << solve(0, n-1, 0, m-1) << endl;
	
	
}

• Subtask 1: 100 / 100