Submission #994811

#	Time	Username	Problem	Language	Result	Execution time	Memory
994811		ducksaysquack	Raisins (IOI09_raisins)	C++98	100 / 100	865 ms	78820 KiB

raisins

#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<int>> v(55,vector<int>(55)), p(55,vector<int>(55));
vector<vector<vector<vector<int>>>> dp(55,vector<vector<vector<int>>>(55,vector<vector<int>>(55,vector<int>(55,1e9))));
int f(int a, int b, int c, int d) {
	if(dp[a][b][c][d] != 1e9) return dp[a][b][c][d];
	if(a==c&&b==d) dp[a][b][c][d] = v[a][b];
	for(int i=a;i<c;i++) dp[a][b][c][d] = min(p[c+1][d+1]-p[a][d+1]-p[c+1][b]+p[a][b]+f(a,b,i,d)+f(i+1,b,c,d),dp[a][b][c][d]);
	for(int i=b;i<d;i++) dp[a][b][c][d] = min(p[c+1][d+1]-p[a][d+1]-p[c+1][b]+p[a][b]+f(a,b,c,i)+f(a,i+1,c,d),dp[a][b][c][d]);
	return dp[a][b][c][d];
}
signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
	for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin >> v[i][j];
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {p[i][j] = p[i-1][j]+p[i][j-1]-p[i-1][j-1]+v[i-1][j-1];}
    f(0,0,n-1,m-1);
	cout << dp[0][0][n-1][m-1]-p[n][m] << '\n';
}

• Subtask 1: 100 / 100