oj.uz

Submission #994811

# Submission time Handle Problem Language Result Execution time Memory
994811 2024-06-08T06:35:16 Z ducksaysquack Raisins (IOI09_raisins) C++
100 / 100
 865 ms 78820 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<int>> v(55,vector<int>(55)), p(55,vector<int>(55));
vector<vector<vector<vector<int>>>> dp(55,vector<vector<vector<int>>>(55,vector<vector<int>>(55,vector<int>(55,1e9))));
int f(int a, int b, int c, int d) {
	if(dp[a][b][c][d] != 1e9) return dp[a][b][c][d];
	if(a==c&&b==d) dp[a][b][c][d] = v[a][b];
	for(int i=a;i<c;i++) dp[a][b][c][d] = min(p[c+1][d+1]-p[a][d+1]-p[c+1][b]+p[a][b]+f(a,b,i,d)+f(i+1,b,c,d),dp[a][b][c][d]);
	for(int i=b;i<d;i++) dp[a][b][c][d] = min(p[c+1][d+1]-p[a][d+1]-p[c+1][b]+p[a][b]+f(a,b,c,i)+f(a,i+1,c,d),dp[a][b][c][d]);
	return dp[a][b][c][d];
}
signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
	for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin >> v[i][j];
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {p[i][j] = p[i-1][j]+p[i][j-1]-p[i-1][j-1]+v[i-1][j-1];}
    f(0,0,n-1,m-1);
	cout << dp[0][0][n-1][m-1]-p[n][m] << '\n';
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 78660 KB Output is correct
2 Correct 120 ms 78676 KB Output is correct
3 Correct 124 ms 78676 KB Output is correct
4 Correct 120 ms 78672 KB Output is correct
5 Correct 118 ms 78676 KB Output is correct
6 Correct 119 ms 78676 KB Output is correct
7 Correct 118 ms 78672 KB Output is correct
8 Correct 126 ms 78776 KB Output is correct
9 Correct 139 ms 78676 KB Output is correct
10 Correct 141 ms 78780 KB Output is correct
11 Correct 139 ms 78676 KB Output is correct
12 Correct 191 ms 78672 KB Output is correct
13 Correct 243 ms 78676 KB Output is correct
14 Correct 147 ms 78732 KB Output is correct
15 Correct 285 ms 78652 KB Output is correct
16 Correct 125 ms 78676 KB Output is correct
17 Correct 177 ms 78676 KB Output is correct
18 Correct 508 ms 78820 KB Output is correct
19 Correct 765 ms 78676 KB Output is correct
20 Correct 865 ms 78632 KB Output is correct