oj.uz

답안 #598409

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
598409 2022-07-18T10:05:44 Z l_reho 건포도 (IOI09_raisins) C++14
10 / 100
 559 ms 26872 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] = 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();
}

Subtask #1
10.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 26708 KB Output is correct
2 Correct 15 ms 26708 KB Output is correct
3 Incorrect 15 ms 26708 KB Output isn't correct
4 Incorrect 14 ms 26704 KB Output isn't correct
5 Incorrect 14 ms 26700 KB Output isn't correct
6 Incorrect 15 ms 26708 KB Output isn't correct
7 Incorrect 16 ms 26712 KB Output isn't correct
8 Incorrect 23 ms 26760 KB Output isn't correct
9 Incorrect 27 ms 26676 KB Output isn't correct
10 Incorrect 27 ms 26768 KB Output isn't correct
11 Incorrect 30 ms 26692 KB Output isn't correct
12 Incorrect 52 ms 26708 KB Output isn't correct
13 Incorrect 79 ms 26784 KB Output isn't correct
14 Incorrect 32 ms 26708 KB Output isn't correct
15 Incorrect 103 ms 26700 KB Output isn't correct
16 Incorrect 26 ms 26756 KB Output isn't correct
17 Incorrect 48 ms 26872 KB Output isn't correct
18 Incorrect 240 ms 26808 KB Output isn't correct
19 Incorrect 435 ms 26792 KB Output isn't correct
20 Incorrect 559 ms 26796 KB Output isn't correct