# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
374689 | Christopher_Rdz | Raisins (IOI09_raisins) | C++17 | 1186 ms | 26112 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;
#define MAX 51
int memo[MAX][MAX][MAX][MAX];
int t[MAX][MAX];
int suma(int i, int j, int a, int b){
return t[a][b] - t[a][j - 1] - t[i - 1][b] + t[i - 1][j - 1];
}
int dp(int i, int j, int a, int b){
if (i == a and j == b){
return 0;
}else{
if (memo[i][j][a][b] == 1000000000){
for (int k = i; k < a; k++){
memo[i][j][a][b] = min(memo[i][j][a][b], dp(i, j, k, b) + dp(k + 1, j, a, b) + suma(i, j, a, b));
}
for (int c = j; c < b; c++){
memo[i][j][a][b] = min(memo[i][j][a][b], dp(i, j, a, c) + dp(i, c + 1, a, b) + suma(i, j, a, b));
}
}
return memo[i][j][a][b];
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
cin >> t[i][j];
t[i][j] += t[i][j - 1] + t[i - 1][j] - t[i - 1][j - 1];
}
}
for (int i = 1; i <= 50; i++){
for (int j = 1; j <= 50; j++){
for (int a = 1; a <= 50; a++){
for (int b = 1; b <= 50; b++){
memo[i][j][a][b] = 1000000000;
}
}
}
}
cout << dp(1, 1, n, m);
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |