# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
874835 |
2023-11-17T21:50:25 Z |
_uros9 |
Raisins (IOI09_raisins) |
C++17 |
|
184 ms |
113784 KB |
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int zb[52][52][52][52],dp[52][52][52][52];
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];
}
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];
}
}
}
}
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+d2==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 |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
1 ms |
8540 KB |
Output is correct |
3 |
Correct |
2 ms |
14680 KB |
Output is correct |
4 |
Correct |
1 ms |
10584 KB |
Output is correct |
5 |
Correct |
2 ms |
18780 KB |
Output is correct |
6 |
Correct |
4 ms |
27184 KB |
Output is correct |
7 |
Correct |
7 ms |
37468 KB |
Output is correct |
8 |
Correct |
6 ms |
43608 KB |
Output is correct |
9 |
Correct |
10 ms |
57948 KB |
Output is correct |
10 |
Correct |
12 ms |
60032 KB |
Output is correct |
11 |
Correct |
9 ms |
47704 KB |
Output is correct |
12 |
Correct |
24 ms |
76488 KB |
Output is correct |
13 |
Correct |
32 ms |
82524 KB |
Output is correct |
14 |
Correct |
12 ms |
52060 KB |
Output is correct |
15 |
Correct |
42 ms |
88668 KB |
Output is correct |
16 |
Correct |
11 ms |
88664 KB |
Output is correct |
17 |
Correct |
24 ms |
97064 KB |
Output is correct |
18 |
Correct |
86 ms |
109144 KB |
Output is correct |
19 |
Correct |
150 ms |
113476 KB |
Output is correct |
20 |
Correct |
184 ms |
113784 KB |
Output is correct |