Submission #598411

#	Time	Username	Problem	Language	Result	Execution time	Memory
598411		l_reho	Raisins (IOI09_raisins)	C++14	100 / 100	670 ms	26852 KiB

raisins

#include <bits/stdc++.h>
using namespace std;

#define ll long long

int N, M;
int dp[51][51][51][51];
vector<vector<int>> pre;
vector<vector<int>> V;



int getSum(int r, int c, int rn, int cm){
	int sm = pre[rn][cm];
	
	if(r > 0)
		sm -= pre[r-1][cm];
	if(c > 0)
		sm -= pre[rn][c-1];
	
	if(r > 0 && c > 0)
		sm += pre[r-1][c-1];
		
	return sm;
	
}

int solver(int r, int c, int n, int m){
	
	if(r == n && c == m) {
		dp[r][c][n][m] = 0;
		return 0;
	}
		
	if(dp[r][c][n][m] != INT_MAX) return dp[r][c][n][m];
	
	// taglio verticale
	for(int i = c; i < m; i++){
		dp[r][c][n][m] = min(dp[r][c][n][m], solver(r, c, n, i) + solver(r, i+1, n, m));
	}
	
	// taglio orrizontale
	
	for(int i = r; i < n; i++){
		dp[r][c][n][m] = min(dp[r][c][n][m], solver(r, c, i, m) + solver(i+1, c, n, m));
		// cout<<"DEBUG-->"<<dp[r][c][n][m]<<endl;
	}
	
	dp[r][c][n][m] += getSum(r, c, n, m);
	// cout<<"DEBUG-->"<<r<<" "<<c<<" "<<n<<" "<<m<<" "<<getSum(r, c, n, m)<<" "<<dp[r][c][n][m]<<endl;
	
	return dp[r][c][n][m];
}


void solve(){
	cin>>N>>M;
	
	V.assign(N, vector<int>(M));
	pre.assign(N, vector<int>(M));
	
	for(int i = 0; i < 51; i++){
		for(int j = 0; j < 51; j++){
			for(int k = 0; k < 51; k++){
				for(int l = 0; l < 51; l++){
					dp[i][j][k][l] = INT_MAX;
				}	
			}	
		}	
	}
	
	for(int i = 0; i < N; i++)
		for(int j = 0; j < M; j++)
			cin>>V[i][j];
	
	for(int j = 0; j < M; j++){
		pre[0][j] = V[0][j];
	}
	

	for(int i = 1; i < N; i++)
		for(int j = 0; j < M; j++)
			pre[i][j] = pre[i-1][j] + V[i][j];
	
	for(int i = 0; i < N; i++)
		for(int j = 1; j < M; j++)
			pre[i][j] += pre[i][j-1];
	
	
	int ans = solver(0, 0, N-1, M-1);
	cout<<ans<<endl;
}

int main(){
	solve();
	
	return 0;
}

• Subtask 1: 100 / 100