# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
659355 | Trisanu_Das | Raisins (IOI09_raisins) | C++17 | 0 ms | 0 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 dp[51][51][51][51], a[51][51], pref[51][51];
int main() {
int n, m; cin >> n >> m;
for(int i = 1; i < n + 1; i++) for(int j = 1; j < m + 1; j++){
cin >> a[i][j];
pref[i][j] = pref[i - 1][j] + pref[i][j - 1] + a[i][j] - pref[i - 1][j - 1];
}
for(int i = 1; i < n + 1; i++) for(int j = 1; j < m + 1; j++) for(int k = 1; k < n - i + 2) for(int l = 1; l < m - j + 2; l++) {
if (i == 1 && j == 1) continue;
int mn = INT_MAX;
for(int x = 1; x < i; x++) mn = min(mn, dp[k][l][x][j] + dp[k + x][l][i - x][j]);
for(int x = 1; x < j; x++) mn = min(mn, dp[k][l][i][x] + dp[k][l + x][i][j - x]);
dp[k][l][i][j] = mn + pref[k + i - 1][l + j - 1] + pref[k - 1][l - 1] - pref[k + i - 1][l - 1] - pref[k - 1][l + j - 1];
}
cout << dp[1][1][n][m];
return 0;
}