oj.uz

Submission #952017

# Submission time Handle Problem Language Result Execution time Memory
952017 2024-03-23T03:46:57 Z Angus_Yeung Raisins (IOI09_raisins) C++17
100 / 100
 211 ms 86688 KB 
#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<ll, ll>
typedef long long ll;
const ll MOD = 1000000007LL;
const ll INF = 1e15;
using namespace std;

ll n, m, a[60][60], a1, b1, a2, b2, tmp;
ll dp[60][60][60][60];

int main() {
	cin.tie(0); cout.tie(0);
	ios::sync_with_stdio(0);
	
	cin >> n >> m;
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			for (int p = 1; p <= n; p++) {
				for (int q = 1; q <= m; q++) dp[i][j][p][q] = INF;
			}
		}
	}
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
			dp[i][j][i][j] = 0;
			a[i][j] += a[i-1][j]+a[i][j-1]-a[i-1][j-1];
		}
	}
	
	for (int dx = 1; dx <= n; dx++) {
		for (int dy = 1; dy <= m; dy++) {
			for (int i = 1; i <= n-dx+1; i++) {
				for (int j = 1; j <= m-dy+1; j++) {
					a1 = i, b1 = j;
					a2 = i+dx-1, b2 = j+dy-1;
					tmp = a[a2][b2]-a[a1-1][b2]-a[a2][b1-1]+a[a1-1][b1-1];
					for (int k = a1; k < a2; k++) {
						dp[a1][b1][a2][b2] = min(dp[a1][b1][a2][b2], dp[a1][b1][k][b2]+dp[k+1][b1][a2][b2]+tmp);
					}
					for (int k = b1; k < b2; k++) {
						dp[a1][b1][a2][b2] = min(dp[a1][b1][a2][b2], dp[a1][b1][a2][k]+dp[a1][k+1][a2][b2]+tmp);
					}
//					cout << a1 << ' ' << b1 << ' ' << a2 << ' ' << b2 << ' ' << tmp << ' ' << dp[a1][b1][a2][b2] << "\n";
				}
			}
//			cout << "\n";
		}
//		cout << "\n";
	}
	
	cout << dp[1][1][n][m] << "\n";
	
	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 2 ms 10708 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 3 ms 18780 KB Output is correct
7 Correct 4 ms 26968 KB Output is correct
8 Correct 5 ms 33116 KB Output is correct
9 Correct 7 ms 41308 KB Output is correct
10 Correct 9 ms 43356 KB Output is correct
11 Correct 7 ms 35164 KB Output is correct
12 Correct 18 ms 55892 KB Output is correct
13 Correct 28 ms 62044 KB Output is correct
14 Correct 9 ms 37212 KB Output is correct
15 Correct 36 ms 64340 KB Output is correct
16 Correct 9 ms 68044 KB Output is correct
17 Correct 18 ms 72284 KB Output is correct
18 Correct 93 ms 82508 KB Output is correct
19 Correct 167 ms 84572 KB Output is correct
20 Correct 211 ms 86688 KB Output is correct