oj.uz

Submission #655598

# Submission time Handle Problem Language Result Execution time Memory
655598 2022-11-04T22:43:02 Z horiseun Raisins (IOI09_raisins) C++11
100 / 100
 695 ms 30316 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
 
int n, m;
int choc[55][55];
int pref[55][55];
bool seen[55][55][55][55];
int cache[55][55][55][55];
 
int dp(int x1, int y1, int x2, int y2) {
	if (x1 == x2 && y1 == y2) return 0;
	if (seen[x1][y1][x2][y2]) return cache[x1][y1][x2][y2];
	
	cache[x1][y1][x2][y2] = INT_MAX;
	seen[x1][y1][x2][y2] = true;
	for (int i = x1; i < x2; i++) {
		cache[x1][y1][x2][y2] = min(cache[x1][y1][x2][y2], dp(x1, y1, i, y2) + dp(i + 1, y1, x2, y2));
	}
	for (int i = y1; i < y2; i++) {
		cache[x1][y1][x2][y2] = min(cache[x1][y1][x2][y2], dp(x1, y1, x2, i) + dp(x1, i + 1, x2, y2));
	}
	cache[x1][y1][x2][y2] += (pref[x2][y2] - pref[x1 - 1][y2] - pref[x2][y1 - 1] + pref[x1 - 1][y1 - 1]);
	
	return cache[x1][y1][x2][y2];
 
}
 
int main() {
 
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> choc[i][j];
		}
	}
 
	pref[1][1] = choc[1][1];
	for (int i = 2; i <= m; i++) {
		pref[1][i] = pref[1][i - 1] + choc[1][i];
	}
	for (int i = 2; i <= n; i++) {
		pref[i][1] = pref[i - 1][1] + choc[i][1];
		for (int j = 2; j <= m; j++) {
			pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + choc[i][j];
		}
	}
 
	cout << dp(1, 1, n, m) << "\n";
 
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 1236 KB Output is correct
7 Correct 1 ms 1364 KB Output is correct
8 Correct 9 ms 4044 KB Output is correct
9 Correct 18 ms 5384 KB Output is correct
10 Correct 24 ms 6356 KB Output is correct
11 Correct 18 ms 5580 KB Output is correct
12 Correct 63 ms 10700 KB Output is correct
13 Correct 117 ms 13452 KB Output is correct
14 Correct 32 ms 6920 KB Output is correct
15 Correct 132 ms 14928 KB Output is correct
16 Correct 13 ms 5192 KB Output is correct
17 Correct 54 ms 10400 KB Output is correct
18 Correct 387 ms 23096 KB Output is correct
19 Correct 561 ms 28424 KB Output is correct
20 Correct 695 ms 30316 KB Output is correct