Submission #741772

#	Time	Username	Problem	Language	Result	Execution time	Memory
741772		MODDI	Raisins (IOI09_raisins)	C++14	100 / 100	253 ms	71976 KiB

raisins

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n, m;
ll mat[55][55], dp[55][55][55][55], pref[55][55];
// dp(i,j,k,l) minimum raisins to cut rectangle(i,j) up to(k,l);
ll f(int x1, int x2, int y1, int y2){
	if(x1 == x2 && y1 == y2)	return 0;
	if(dp[x1][x2][y1][y2] != -1)	return dp[x1][x2][y1][y2];
	
	ll	ans = 1e18;
	for(int i=x1; i < x2;i++){
		ans = min(ans, f(x1, i, y1, y2) + f(i+1, x2, y1, y2));
	}
	for(int i = y1; i < y2; i++){
		ans = min(ans, f(x1, x2, y1, i) + f(x1, x2, i+1, y2));
	}
	return dp[x1][x2][y1][y2] = ans + (pref[x2][y2] - pref[x1-1][y2] - pref[x2][y1-1] + pref[x1-1][y1-1]);
}
int main(){
	cin>>n>>m;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			cin>>mat[i][j];
	memset(dp, -1, sizeof dp);
	memset(pref, 0, sizeof pref);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			pref[i][j] = pref[i-1][j] + pref[i][j-1] + mat[i][j] - pref[i-1][j-1];
		}
	}
	cout<<f(1, n, 1, m)<<endl;
	return 0;
}

• Subtask 1: 100 / 100