oj.uz

Submission #994806

# Submission time Handle Problem Language Result Execution time Memory
994806 2024-06-08T06:16:52 Z ducksaysquack Raisins (IOI09_raisins) C++
25 / 100
 5000 ms 78760 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(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];
}

Subtask #1
25.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 78720 KB Output is correct
2 Correct 126 ms 78612 KB Output is correct
3 Correct 120 ms 78676 KB Output is correct
4 Correct 121 ms 78672 KB Output is correct
5 Correct 209 ms 78672 KB Output is correct
6 Execution timed out 5047 ms 78672 KB Time limit exceeded
7 Execution timed out 5049 ms 78676 KB Time limit exceeded
8 Execution timed out 5062 ms 78760 KB Time limit exceeded
9 Execution timed out 5040 ms 78672 KB Time limit exceeded
10 Execution timed out 5061 ms 78608 KB Time limit exceeded
11 Execution timed out 5040 ms 78672 KB Time limit exceeded
12 Execution timed out 5020 ms 78612 KB Time limit exceeded
13 Execution timed out 5067 ms 78672 KB Time limit exceeded
14 Execution timed out 5042 ms 78744 KB Time limit exceeded
15 Execution timed out 5076 ms 78676 KB Time limit exceeded
16 Execution timed out 5088 ms 78672 KB Time limit exceeded
17 Execution timed out 5030 ms 78676 KB Time limit exceeded
18 Execution timed out 5018 ms 78676 KB Time limit exceeded
19 Execution timed out 5048 ms 78688 KB Time limit exceeded
20 Execution timed out 5046 ms 78672 KB Time limit exceeded