# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
598409 | l_reho | Raisins (IOI09_raisins) | C++14 | 559 ms | 26872 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 ll long long
int N, M;
int dp[51][51][51][51];
vector<vector<int>> pre;
vector<vector<int>> V;
int getSum(int r, int c, int rn, int cm){
int sm = pre[rn][cm];
if(r > 0)
sm -= pre[r-1][cm];
if(c > 0)
sm -= pre[rn][c-1];
if(r > 0 && c > 0)
sm += pre[r-1][c-1];
return sm;
}
int solver(int r, int c, int n, int m){
if(r == n && c == m) {
dp[r][c][n][m] = 0;
return 0;
}
if(dp[r][c][n][m] != INT_MAX) return dp[r][c][n][m];
// taglio verticale
for(int i = c; i < m; i++){
dp[r][c][n][m] = solver(r, c, n, i) + solver(r, i+1, n, m);
}
// taglio orrizontale
for(int i = r; i < n; i++){
dp[r][c][n][m] = min(dp[r][c][n][m], solver(r, c, i, m) + solver(i+1, c, n, m));
// cout<<"DEBUG-->"<<dp[r][c][n][m]<<endl;
}
dp[r][c][n][m] += getSum(r, c, n, m);
// cout<<"DEBUG-->"<<r<<" "<<c<<" "<<n<<" "<<m<<" "<<getSum(r, c, n, m)<<" "<<dp[r][c][n][m]<<endl;
return dp[r][c][n][m];
}
void solve(){
cin>>N>>M;
V.assign(N, vector<int>(M));
pre.assign(N, vector<int>(M));
for(int i = 0; i < 51; i++){
for(int j = 0; j < 51; j++){
for(int k = 0; k < 51; k++){
for(int l = 0; l < 51; l++){
dp[i][j][k][l] = INT_MAX;
}
}
}
}
for(int i = 0; i < N; i++)
for(int j = 0; j < M; j++)
cin>>V[i][j];
for(int j = 0; j < M; j++){
pre[0][j] = V[0][j];
}
for(int i = 1; i < N; i++)
for(int j = 0; j < M; j++)
pre[i][j] = pre[i-1][j] + V[i][j];
for(int i = 0; i < N; i++)
for(int j = 1; j < M; j++)
pre[i][j] += pre[i][j-1];
int ans = solver(0, 0, N-1, M-1);
cout<<ans<<endl;
}
int main(){
solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |