Submission #798036

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
798036	2023-07-30T10:02:41 Z	aymanrs	Raisins (IOI09_raisins)	C++14	100 / 100	120 ms	24788 KB

raisins

#include<bits/stdc++.h>
const int MOD = 1e9+7;
using namespace std;
void solve(){
	int n, m;
	cin >> n >> m;
	int dp[n][m][n][m];
	int pr[n][m];
	for(int i = 0;i < n;i++) for(int j = 0;j < m;j++) {
		cin >> pr[i][j];
		dp[0][0][i][j] = 0;
		if(i) pr[i][j] += pr[i-1][j];
		if(j) {
			pr[i][j] += pr[i][j-1];
			if(i) pr[i][j] -= pr[i-1][j-1];
		}
	}
	for(int h = 0;h < n;h++){
		for(int w = h ? 0 : 1;w < m;w++){
			for(int i = 0;i+h < n;i++){
				for(int j = 0;j+w < m;j++){
					dp[h][w][i][j] = pr[i+h][j+w]-(i ? pr[i-1][j+w] : 0)-(j ? pr[i+h][j-1] : 0)+(i&&j ? pr[i-1][j-1] : 0);
					int x = INT_MAX;
					for(int k = 0;k < h;k++) x = min(x, dp[k][w][i][j]+dp[h-k-1][w][i+k+1][j]);
					for(int k = 0;k < w;k++) x = min(x, dp[h][k][i][j]+dp[h][w-k-1][i][j+k+1]);
					dp[h][w][i][j] += x;
				}
			}
		}
	}
	cout << dp[n-1][m-1][0][0] << '\n';
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	320 KB	Output is correct
6	Correct	1 ms	320 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	2 ms	980 KB	Output is correct
9	Correct	3 ms	1364 KB	Output is correct
10	Correct	4 ms	1748 KB	Output is correct
11	Correct	5 ms	1620 KB	Output is correct
12	Correct	13 ms	4052 KB	Output is correct
13	Correct	21 ms	6100 KB	Output is correct
14	Correct	6 ms	2260 KB	Output is correct
15	Correct	25 ms	7252 KB	Output is correct
16	Correct	2 ms	980 KB	Output is correct
17	Correct	10 ms	3284 KB	Output is correct
18	Correct	64 ms	14840 KB	Output is correct
19	Correct	110 ms	21960 KB	Output is correct
20	Correct	120 ms	24788 KB	Output is correct