Submission #1197617

#TimeUsernameProblemLanguageResultExecution timeMemory
1197617HanksburgerRaisins (IOI09_raisins)C++20
100 / 100
58 ms15684 KiB
#include <bits/stdc++.h> using namespace std; int a[55][55], b[55][55], dp[55][55][55][55]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; for (int i=1; i<=n; i++) { for (int j=1; j<=m; j++) { cin >> a[i][j]; b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j]; } } for (int id=0; id<n; id++) { for (int il=1; il<=n-id; il++) { int ir=il+id; for (int jd=0; jd<m; jd++) { for (int jl=1; jl<=m-jd; jl++) { int jr=jl+jd; if (il==ir && jl==jr) continue; dp[il][ir][jl][jr]=1e9; for (int i=il; i<ir; i++) dp[il][ir][jl][jr]=min(dp[il][ir][jl][jr], dp[il][i][jl][jr]+dp[i+1][ir][jl][jr]); for (int j=jl; j<jr; j++) dp[il][ir][jl][jr]=min(dp[il][ir][jl][jr], dp[il][ir][jl][j]+dp[il][ir][j+1][jr]); dp[il][ir][jl][jr]+=b[ir][jr]-b[ir][jl-1]-b[il-1][jr]+b[il-1][jl-1]; } } } } cout << dp[1][n][1][m]; }
#Verdict Execution timeMemoryGrader output
Fetching results...