Submission #255485

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
255485	2020-08-01T06:13:20 Z	shrek12357	Raisins (IOI09_raisins)	C++14	100 / 100	367 ms	20984 KB

raisins

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <fstream>
#include <queue>
using namespace std;

int pre[51][51];


int calc(int a, int b, int c, int d) {
	int ans = pre[c][d];
	if (a > 0) {
		ans -= pre[a - 1][d];
	}
	if (b > 0) {
		ans -= pre[c][b - 1];
	}
	if (a > 0 && b > 0) {
		ans += pre[a - 1][b - 1];
	}
	return ans;
}

int main() {
	int n, m;
	cin >> n >> m;
	int grid[51][51];
	int dp[51][51][51][51];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> grid[i][j];
		}
	}
	pre[0][0] = grid[0][0];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (i == 0 && j == 0) {
				continue;
			}
			if (i == 0) {
				pre[i][j] = pre[i][j - 1] + grid[i][j];
			}
			else if (j == 0) {
				pre[i][j] = pre[i - 1][j] + grid[i][j];
			}
			else {
				pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + grid[i][j];
			}	
		}
	}
	for (int len1 = 0; len1 < n; len1++) {
		for (int len2 = 0; len2 < m; len2++) {
			for (int i = 0; i < n - len1; i++) {
				for (int j = 0; j < m - len2; j++) {
					if (len1 == 0 && len2 == 0) {
						dp[i][j][i + len1][j + len2] = 0;
					}
					else {
						dp[i][j][i + len1][j + len2] = INT_MAX;
						for (int a = 0; a < len1; a++) {
							dp[i][j][i + len1][j + len2] = min(dp[i][j][i + len1][j + len2], dp[i][j][i + a][j + len2] + dp[i + a + 1][j][i + len1][j + len2] + calc(i, j, i + len1, j + len2));
						}
						for (int a = 0; a < len2; a++) {
							dp[i][j][i + len1][j + len2] = min(dp[i][j][i + len1][j + len2], dp[i][j][i + len1][j + a] + dp[i][j + a + 1][i + len1][j + len2] + calc(i, j, i + len1, j + len2));
						}
					}
				}
			}
		}
	}
	cout << dp[0][0][n - 1][m - 1] << endl;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	0 ms	512 KB	Output is correct
6	Correct	1 ms	896 KB	Output is correct
7	Correct	1 ms	1024 KB	Output is correct
8	Correct	3 ms	2688 KB	Output is correct
9	Correct	7 ms	3712 KB	Output is correct
10	Correct	9 ms	4352 KB	Output is correct
11	Correct	7 ms	3840 KB	Output is correct
12	Correct	28 ms	7416 KB	Output is correct
13	Correct	51 ms	9464 KB	Output is correct
14	Correct	11 ms	4736 KB	Output is correct
15	Correct	64 ms	10488 KB	Output is correct
16	Correct	5 ms	3584 KB	Output is correct
17	Correct	26 ms	7296 KB	Output is correct
18	Correct	184 ms	15992 KB	Output is correct
19	Correct	306 ms	19832 KB	Output is correct
20	Correct	367 ms	20984 KB	Output is correct