# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
771872 | cnastea | Raisins (IOI09_raisins) | C++14 | 829 ms | 54360 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 a[50][50];
int d[50][50][50][50];
bool b[50][50][50][50];
int f(int p, int q, int r, int s){
if(p == r && q == s) {
return 0;
}
if (b[p][q][r][s]) {
return d[p][q][r][s];
}
else b[p][q][r][s] = 1;
int m = 1e9, t = 0;
for(int i = p; i <= r; i++){
for(int j = q; j <= s; j++){
t += a[i][j];
}
}
for(int i = p; i <= r; i++){
int x, y;
x = f(p, q, i-1, s);
y = f(i, q, r, s);
m = min(m, x + y + t);
}
for(int i = q; i <= s; i++){
int x, y;
x = f(p, q, r, i-1);
y = f(p, i, r, s);
m = min(m, x + y + t);
}
d[p][q][r][s] = m;
return m;
}
int main()
{
int n, m;
cin >> n >> m;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> a[i][j];
}
}
cout << f(0, 0, n-1, m-1);
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |