Submission #844795

#TimeUsernameProblemLanguageResultExecution timeMemory
844795asdfgraceRaisins (IOI09_raisins)C++17
100 / 100
77 ms36440 KiB
#include <bits/stdc++.h> using namespace std; const int inf = 0x3f3f3f3f; const int N = 55; int dp[N][N][N][N]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; vector<vector<int>> a(n, vector<int>(m)); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { cin >> a[i][j]; } } vector<vector<int>> psum = a; for (int i = 0; i < n; ++i) { for (int j = 1; j < m; ++j) { psum[i][j] += psum[i][j - 1]; } } for (int j = 0; j < m; ++j) { for (int i = 1; i < n; ++i) { psum[i][j] += psum[i - 1][j]; } } memset(dp, 0x3f, sizeof(dp)); for (int il = n - 1; il >= 0; --il) { for (int ir = il; ir < n; ++ir) { for (int jl = m - 1; jl >= 0; --jl) { for (int jr = jl; jr < m; ++jr) { int sum = (il && jl ? psum[il - 1][jl - 1] : 0) + psum[ir][jr] - (il ? psum[il - 1][jr] : 0) - (jl ? psum[ir][jl - 1] : 0); if (il == ir && jl == jr) { dp[il][ir][jl][jr] = 0; continue; } for (int im = il; im < ir; ++im) { dp[il][ir][jl][jr] = min(dp[il][ir][jl][jr], dp[il][im][jl][jr] + dp[im + 1][ir][jl][jr] + sum); } for (int jm = jl; jm < jr; ++jm) { dp[il][ir][jl][jr] = min(dp[il][ir][jl][jr], dp[il][ir][jl][jm] + dp[il][ir][jm + 1][jr] + sum); } } } } } cout << dp[0][n - 1][0][m - 1] << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...