oj.uz

답안 #598411

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
598411 2022-07-18T10:20:07 Z l_reho 건포도 (IOI09_raisins) C++14
100 / 100
 670 ms 26852 KB 
#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

# 결과 실행 시간 메모리 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