Submission #952017

#	Time	Username	Problem	Language	Result	Execution time	Memory
952017		Angus_Yeung	Raisins (IOI09_raisins)	C++17	100 / 100	211 ms	86688 KiB

raisins

#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 / 100