# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
867595 | Bula | Raisins (IOI09_raisins) | C++17 | 5097 ms | 35420 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int n, m, x[55][55], dp[55][55][55][55], pref[55][55];
int rec(int a, int b, int A, int B){
if(a == A && b == B){
return 0;
}
int sum = pref[A][B] + pref[a - 1][b - 1] - pref[a - 1][B] - pref[A][b - 1];
for(int i = a; i < A; i++){
dp[a][b][A][B] = min(dp[a][b][A][B], sum + rec(a, b, i, B) + rec(i + 1, b, A, B));
}
for(int i = b; i < B; i++){
dp[a][b][A][B] = min(dp[a][b][A][B], sum + rec(a, b, A, i) + rec(a, i + 1, A, B));
}
return dp[a][b][A][B];
}
main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= 50; i++){
for(int j = 1; j <= 50; j++){
for(int k = 1; k <= 50; k++){
for(int l = 1; l <= 50; l++){
dp[i][j][k][l] = INT_MAX;
}
}
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> x[i][j];
dp[i][j][i][j] = 0;
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
pref[i][j] = x[i][j] + pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
}
}
cout << rec(1, 1, n, m) << endl;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |