Submission #211245

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
211245	2020-03-19T18:04:35 Z	socho	Raisins (IOI09_raisins)	C++14	100 / 100	1072 ms	36344 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	36096 KB	Output is correct
2	Correct	24 ms	36096 KB	Output is correct
3	Correct	21 ms	36096 KB	Output is correct
4	Correct	23 ms	36096 KB	Output is correct
5	Correct	21 ms	36096 KB	Output is correct
6	Correct	23 ms	36096 KB	Output is correct
7	Correct	22 ms	36096 KB	Output is correct
8	Correct	33 ms	36096 KB	Output is correct
9	Correct	43 ms	36096 KB	Output is correct
10	Correct	53 ms	36096 KB	Output is correct
11	Correct	48 ms	36096 KB	Output is correct
12	Correct	115 ms	36096 KB	Output is correct
13	Correct	179 ms	36224 KB	Output is correct
14	Correct	62 ms	36096 KB	Output is correct
15	Correct	239 ms	36216 KB	Output is correct
16	Correct	35 ms	36224 KB	Output is correct
17	Correct	105 ms	36344 KB	Output is correct
18	Correct	589 ms	36096 KB	Output is correct
19	Correct	910 ms	36216 KB	Output is correct
20	Correct	1072 ms	36224 KB	Output is correct