# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
415268 | Antekb | Raisins (IOI09_raisins) | C++14 | 368 ms | 52664 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;
const int N=51;
long long dp[N][N][N][N], sum[N][N][N][N];
int tab[N][N];
int main(){
int n, m;
cin>>n>>m;
for(int i=0; i<n; i++){
for(int j=0; j<m;j ++){
cin>>sum[i][i][j][j];
}
}
for(int d1=0; d1<n; d1++){
for(int i=0; i<n-d1; i++){
for(int d2=0; d2<m; d2++){
for(int j=0; j<m-d2; j++){
if(d1==0 && d2==0)continue;
dp[i][i+d1][j][j+d2]=1e18;
if(d1){
sum[i][i+d1][j][j+d2]=sum[i][i][j][j+d2]+sum[i+1][i+d1][j][j+d2];
for(int k=0; k<d1; k++){
dp[i][i+d1][j][j+d2]=min(dp[i][i+d1][j][j+d2], dp[i][i+k][j][j+d2]+dp[i+k+1][i+d1][j][j+d2]);
}
}
if(d2){
sum[i][i+d1][j][j+d2]=sum[i][i+d1][j][j]+sum[i][i+d1][j+1][j+d2];
for(int k=0; k<d2; k++){
dp[i][i+d1][j][j+d2]=min(dp[i][i+d1][j][j+d2], dp[i][i+d1][j][j+k]+dp[i][i+d1][j+k+1][j+d2]);
}
}
dp[i][i+d1][j][j+d2]+=sum[i][i+d1][j][j+d2];
//cout<<i<<" "<<i+d1<<" "<<j<<" "<<j+d2<<" "<<dp[i][i+d1][j][j+d2]<<" "<<sum[i][i+d1][j][j+d2]<<"\n";
}
}
}
}
cout<<dp[0][n-1][0][m-1];
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |