Submission #741772

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
741772	2023-05-14T21:09:41 Z	MODDI	Raisins (IOI09_raisins)	C++14	100 / 100	253 ms	71976 KB

raisins

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n, m;
ll mat[55][55], dp[55][55][55][55], pref[55][55];
// dp(i,j,k,l) minimum raisins to cut rectangle(i,j) up to(k,l);
ll f(int x1, int x2, int y1, int y2){
	if(x1 == x2 && y1 == y2)	return 0;
	if(dp[x1][x2][y1][y2] != -1)	return dp[x1][x2][y1][y2];
	
	ll	ans = 1e18;
	for(int i=x1; i < x2;i++){
		ans = min(ans, f(x1, i, y1, y2) + f(i+1, x2, y1, y2));
	}
	for(int i = y1; i < y2; i++){
		ans = min(ans, f(x1, x2, y1, i) + f(x1, x2, i+1, y2));
	}
	return dp[x1][x2][y1][y2] = ans + (pref[x2][y2] - pref[x1-1][y2] - pref[x2][y1-1] + pref[x1-1][y1-1]);
}
int main(){
	cin>>n>>m;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			cin>>mat[i][j];
	memset(dp, -1, sizeof dp);
	memset(pref, 0, sizeof pref);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			pref[i][j] = pref[i-1][j] + pref[i][j-1] + mat[i][j] - pref[i-1][j-1];
		}
	}
	cout<<f(1, n, 1, m)<<endl;
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	71892 KB	Output is correct
2	Correct	27 ms	71872 KB	Output is correct
3	Correct	27 ms	71968 KB	Output is correct
4	Correct	28 ms	71908 KB	Output is correct
5	Correct	30 ms	71860 KB	Output is correct
6	Correct	29 ms	71884 KB	Output is correct
7	Correct	32 ms	71860 KB	Output is correct
8	Correct	33 ms	71856 KB	Output is correct
9	Correct	32 ms	71884 KB	Output is correct
10	Correct	34 ms	71852 KB	Output is correct
11	Correct	33 ms	71888 KB	Output is correct
12	Correct	50 ms	71952 KB	Output is correct
13	Correct	57 ms	71896 KB	Output is correct
14	Correct	47 ms	71944 KB	Output is correct
15	Correct	91 ms	71844 KB	Output is correct
16	Correct	34 ms	71892 KB	Output is correct
17	Correct	43 ms	71852 KB	Output is correct
18	Correct	141 ms	71892 KB	Output is correct
19	Correct	214 ms	71972 KB	Output is correct
20	Correct	253 ms	71976 KB	Output is correct