Submission #659805

#	Time	Username	Problem	Language	Result	Execution time	Memory
659805		Tob	Raisins (IOI09_raisins)	C++14	100 / 100	659 ms	83016 KiB

raisins

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 57;

int n, m;
ll mat[N][N], ps[N][N];
ll dp[N][N][N][N];

ll f(int a1, int b1, int a2, int b2) {
	return ps[a2][b2] - ps[a1-1][b2] - ps[a2][b1-1] + ps[a1-1][b1-1];
}

ll DP(int a1, int b1, int a2, int b2) {
	if (dp[a1][b1][a2][b2] != -1) return dp[a1][b1][a2][b2];
	if (a1 == a2 && b1 == b2) {
		dp[a1][b1][a2][b2] = 0;
		return 0;
	}
	ll mn = 1e18;
	for (int i = a1; i < a2; i++) {
		mn = min(mn, DP(a1, b1, i, b2) + DP(i+1, b1, a2, b2));
	}
	for (int i = b1; i < b2; i++) {
		mn = min(mn, DP(a1, b1, a2, i) + DP(a1, i+1, a2, b2));
	}
	dp[a1][b1][a2][b2] = mn + f(a1, b1, a2, b2);
	return dp[a1][b1][a2][b2];
}

int main () {
	memset(dp, -1, sizeof dp);
	
	cin >> n >> m;
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> mat[i][j];
			ps[i][j] = ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1] + mat[i][j];
		}
	}
	
	cout << DP(1, 1, n, m);
	
	return 0;
}

• Subtask 1: 100 / 100