oj.uz

Submission #366749

# Submission time Handle Problem Language Result Execution time Memory
366749 2021-02-15T09:09:41 Z kostia244 Raisins (IOI09_raisins) C++17
100 / 100
 1056 ms 36332 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
const int maxn = 55;
int n, m, a[maxn][maxn], p[maxn][maxn];
int dp[maxn][maxn][maxn][maxn];
int f(int xl, int xr, int yl, int yr) {
	int &ans = dp[xl][xr][yl][yr];
	if(ans >= 0) return ans;
	if(xl == xr && yl == yr) return 0;
	ans = 1<<30;
	for(int c = xl; c < xr; c++) ans = min(ans, f(xl, c, yl, yr) + f(c+1, xr, yl, yr));
	for(int c = yl; c < yr; c++) ans = min(ans, f(xl, xr, yl, c) + f(xl, xr, c+1, yr));
	--xl,--yl;ans += p[xr][yr] - p[xl][yr] - p[xr][yl] + p[xl][yl];
	return ans;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			cin >> a[i][j], p[i][j] = a[i][j] + p[i-1][j];
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			p[i][j] += p[i][j-1];
	memset(dp, -1, sizeof dp);
	cout << f(1, n, 1, m);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 36204 KB Output is correct
2 Correct 20 ms 36204 KB Output is correct
3 Correct 20 ms 36204 KB Output is correct
4 Correct 20 ms 36204 KB Output is correct
5 Correct 20 ms 36204 KB Output is correct
6 Correct 20 ms 36204 KB Output is correct
7 Correct 20 ms 36204 KB Output is correct
8 Correct 30 ms 36204 KB Output is correct
9 Correct 42 ms 36220 KB Output is correct
10 Correct 50 ms 36204 KB Output is correct
11 Correct 44 ms 36204 KB Output is correct
12 Correct 115 ms 36204 KB Output is correct
13 Correct 190 ms 36204 KB Output is correct
14 Correct 62 ms 36332 KB Output is correct
15 Correct 233 ms 36332 KB Output is correct
16 Correct 36 ms 36204 KB Output is correct
17 Correct 106 ms 36204 KB Output is correct
18 Correct 567 ms 36332 KB Output is correct
19 Correct 889 ms 36204 KB Output is correct
20 Correct 1056 ms 36204 KB Output is correct