Submission #924199

#	Time	Username	Problem	Language	Result	Execution time	Memory
924199		bananade	Raisins (IOI09_raisins)	C++17	100 / 100	156 ms	129508 KiB

raisins

#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[55][55][55][55];
int n, m;
int arr[55][55];
int ARR[55][55][55][55];
int pref[55][55];

int DP(int a, int b, int c, int d) {
	if(dp[a][b][c][d] != -1) {
		return dp[a][b][c][d];
	}
	int mini = 1e9;
	for(int i = a; i < b; i++) {
		mini = min(mini, DP(a, i, c, d) + DP(i + 1, b, c, d));
	}
	for(int i = c; i < d; i++) {
		mini = min(mini, DP(a, b, c, i) + DP(a, b, i + 1, d));
	}
	mini += pref[b][d] + pref[a - 1][c - 1] - pref[b][c - 1] - pref[a - 1][d];
	//cout << mini << " " << a << " " << b << " " << c << " " << d << "\n";
	return dp[a][b][c][d] = mini;
}

signed main() {
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin >> n >> m;
	memset(dp, -1, sizeof(dp));
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			cin >> arr[i][j];
			dp[i][i][j][j] = 0;
			ARR[i][i][j][j] = arr[i][j];
		}
	}
	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] - pref[i - 1][j - 1] + arr[i][j];
		}
	}
	
	cout << DP(1, n, 1, m) << "\n";
	
}

• Subtask 1: 100 / 100