Submission #239364

#TimeUsernameProblemLanguageResultExecution timeMemory
239364DavidDamianRaisins (IOI09_raisins)C++11
100 / 100
751 ms30328 KiB
#include <bits/stdc++.h> using namespace std; int n,m; ///Dynamic Programming ///Top-Down ///Determine the minimum number of raisins needed to pay (sums) int A[55][55]; int sum[55][55]; int memo[55][55][55][55]; int getSum(int i,int j,int a,int b) { int total=sum[j][b]-sum[j][a-1]-sum[i-1][b]+sum[i-1][a-1]; return total; } int MinCost(int i,int j,int a,int b) { if(i==j && a==b) return 0; if(memo[i][j][a][b]==-1){ int minimum=INT_MAX; for(int i_nxt=i;i_nxt<j;i_nxt++){ minimum=min(minimum,MinCost(i,i_nxt,a,b) +MinCost(i_nxt+1,j,a,b) +getSum(i,j,a,b)); } for(int a_nxt=a;a_nxt<b;a_nxt++){ minimum=min(minimum,MinCost(i,j,a,a_nxt) +MinCost(i,j,a_nxt+1,b) +getSum(i,j,a,b)); } memo[i][j][a][b]=minimum; } return memo[i][j][a][b]; } int main() { ios_base::sync_with_stdio(0);cin.tie(0); cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ for(int a=1;a<=m;a++){ for(int b=1;b<=m;b++){ memo[i][j][a][b]=-1; } } } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>A[i][j]; sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+A[i][j]; } } int total=MinCost(1,n,1,m); cout<<total<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...