Submission #598409

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
598409	2022-07-18T10:05:44 Z	l_reho	Raisins (IOI09_raisins)	C++14	10 / 100	559 ms	26872 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] = 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

#	Verdict	Execution time	Memory	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