제출 #374678

#제출 시각아이디문제언어결과실행 시간메모리
374678meperdonas203건포도 (IOI09_raisins)C++17
100 / 100
1161 ms27116 KiB
#include <bits/stdc++.h> using namespace std; int matriz[52][52]; int memo[52][52][52][52]; int n,m; int suma(int i,int j,int a,int b){ return (matriz[a][b]+matriz[i-1][j-1])-(matriz[a][j-1]+matriz[i-1][b]); } int dp(int i,int j,int a,int b){ if(i==a and j==b )return 0; if(memo[i][j][a][b]==200000000){ for(int k=i;k<a;k++){ memo[i][j][a][b]=min(memo[i][j][a][b],dp(i,j,k,b)+dp(k+1,j,a,b)+suma(i,j,a,b)); } for(int c=j;c<b;c++){ memo[i][j][a][b]=min(memo[i][j][a][b],dp(i,j,a,c)+dp(i,c+1,a,b)+suma(i,j,a,b)); } } 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<=50;i++){ for(int j=1;j<=50;j++){ for(int a=1;a<=50;a++){ for(int b=1;b<=50;b++){ memo[i][j][a][b]=200000000; } } } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>matriz[i][j]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ matriz[i][j]+=matriz[i][j-1]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ matriz[i][j]+=matriz[i-1][j]; } } cout<<dp(1,1,n,m); }
#Verdict Execution timeMemoryGrader output
Fetching results...