Submission #1201859

#TimeUsernameProblemLanguageResultExecution timeMemory
1201859PlayVoltzRaisins (IOI09_raisins)C++20
100 / 100
494 ms72092 KiB
#include <cstdio> #include <stdio.h> #include <stdbool.h> #include <iostream> #include <map> #include <vector> #include <climits> #include <stack> #include <string> #include <queue> #include <algorithm> #include <set> #include <unordered_set> #include <unordered_map> #include <cmath> #include <cctype> #include <bitset> #include <iomanip> #include <cstring> #include <numeric> #include <cassert> using namespace std; #define int long long #define pii pair<int, int> #define mp make_pair #define pb push_back #define fi first #define se second int n, m, dp[55][55][55][55]; vector<vector<int> > vect; int cut(int l, int r, int u, int d){ if (l==r&&u==d)return 0; if (dp[l][r][u][d]!=-1)return dp[l][r][u][d]; int res=LLONG_MAX/2; for (int i=l; i<r; ++i)res=min(res, cut(l, i, u, d)+cut(i+1, r, u, d)); for (int i=u; i<d; ++i)res=min(res, cut(l, r, u, i)+cut(l, r, i+1, d)); return dp[l][r][u][d]=res+vect[d][r]-vect[d][l-1]-vect[u-1][r]+vect[u-1][l-1]; } int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m; memset(dp, -1, sizeof(dp)); vect.resize(n+1, vector<int>(m+1, 0)); for (int i=1; i<=n; ++i)for (int j=1; j<=m; ++j)cin>>vect[i][j], vect[i][j]+=vect[i][j-1]+vect[i-1][j]-vect[i-1][j-1]; cout<<cut(1, m, 1, n); }
#Verdict Execution timeMemoryGrader output
Fetching results...