# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
874823 | _uros9 | Raisins (IOI09_raisins) | C++17 | 321 ms | 106344 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>
#define int long long
#define endl '\n'
using namespace std;
signed main()
{
int n,m;
cin >> n >> m;
vector<vector<int>> matr(n+1,vector<int>(m+1));
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++)
cin >> matr[i][j];
}
int zb[n+1][m+1][n+1][m+1];
for(int i=0; i<=n; i++){//pravljenje
for(int j=0; j<=m; j++){
for(int ii=0; ii<=n; ii++){
for(int jj=0; jj<=m; jj++)
zb[i][j][ii][jj]=0;
}
}
}
for(int y1=1; y1<=n; y1++){
for(int x1=1; x1<=m; x1++){
for(int y2=y1; y2<=n; y2++){
for(int x2=x1; x2<=m; x2++){
zb[y1][x1][y2][x2]=(y2-1<y1?0:zb[y1][x1][y2-1][x2])+(x2-1<x1?0:zb[y1][x1][y2][x2-1])-(((y2-1<y1)||(x2-1<x1))?0:zb[y1][x1][y2-1][x2-1])+matr[y2][x2];
}
}
}
}
int dp[n+1][m+1][n+1][m+1];
for(int i=0; i<=n; i++){//pravljenje
for(int j=0; j<=m; j++){
for(int ii=0; ii<=n; ii++){
for(int jj=0; jj<=m; jj++)
dp[i][j][ii][jj]=1000000000000000000;
}
}
}
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++)
dp[i][j][i][j]=0;//matr[i][j];
}
for(int d1=0; d1<=n; d1++){
for(int d2=0; d2<=m; d2++){
for(int y1=1; y1+d1<=n; y1++){
for(int x1=1; x1+d2<=m; x1++){
if(d1+d1==0) continue;
int sum=zb[y1][x1][y1+d1][x1+d2];
for(int k=0; k<d2; k++){
dp[y1][x1][y1+d1][x1+d2]=min(dp[y1][x1][y1+d1][x1+d2],sum+dp[y1][x1][y1+d1][x1+k]+dp[y1][x1+k+1][y1+d1][x1+d2]);
}
for(int k=0; k<d1; k++){
dp[y1][x1][y1+d1][x1+d2]=min(dp[y1][x1][y1+d1][x1+d2],sum+dp[y1][x1][y1+k][x1+d2]+dp[y1+k+1][x1][y1+d1][x1+d2]);
}
}
}
}
}
cout << dp[1][1][n][m];
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |