Submission #598411

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
598411	2022-07-18T10:20:07 Z	l_reho	Raisins (IOI09_raisins)	C++14	100 / 100	670 ms	26852 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	26708 KB	Output is correct
2	Correct	16 ms	26708 KB	Output is correct
3	Correct	17 ms	26720 KB	Output is correct
4	Correct	16 ms	26752 KB	Output is correct
5	Correct	16 ms	26708 KB	Output is correct
6	Correct	15 ms	26700 KB	Output is correct
7	Correct	15 ms	26736 KB	Output is correct
8	Correct	22 ms	26708 KB	Output is correct
9	Correct	23 ms	26708 KB	Output is correct
10	Correct	27 ms	26784 KB	Output is correct
11	Correct	26 ms	26700 KB	Output is correct
12	Correct	54 ms	26768 KB	Output is correct
13	Correct	98 ms	26852 KB	Output is correct
14	Correct	34 ms	26764 KB	Output is correct
15	Correct	124 ms	26772 KB	Output is correct
16	Correct	21 ms	26676 KB	Output is correct
17	Correct	47 ms	26708 KB	Output is correct
18	Correct	266 ms	26780 KB	Output is correct
19	Correct	546 ms	26784 KB	Output is correct
20	Correct	670 ms	26784 KB	Output is correct