Submission #221234

#TimeUsernameProblemLanguageResultExecution timeMemory
221234tatyamRaisins (IOI09_raisins)C++17
100 / 100
315 ms25976 KiB
#include <bits/stdc++.h> using namespace std; using uint = unsigned; #define name3(a,b,c,d,...) d #define rep1(b) for(int i = 0; i < b; i++) #define rep2(i,b) for(int i = 0; i < b; i++) #define rep3(i,a,b) for(int i = a; i < b; i++) #define rep(...) name3(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__) #define each(i,a) for(auto&& i : a) #define all(a) begin(a), end(a) template<class T, class U> bool chmin(T& a, const U& b){ if(a > b){ a = b; return 1; } return 0; } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n, m; cin >> n >> m; uint a[51][51] = {}; rep(n) rep(j, m) cin >> a[i + 1][j + 1]; rep(n + 1) rep(j, m) a[i][j + 1] += a[i][j]; rep(j, m + 1) rep(n) a[i + 1][j] += a[i][j]; static uint dp[50][50][51][51]; memset(dp, 0xff, sizeof(dp)); rep(50) rep(j, 50) dp[i][j][i + 1][j + 1] = 0; rep(x, 1, n + 1) rep(y, 1, m + 1) if(x != 1 || y != 1){ rep(x1, n - x + 1){ int x2 = x1 + x; rep(y1, m - y + 1){ int y2 = y1 + y; rep(x3, x1 + 1, x2) chmin(dp[x1][y1][x2][y2], dp[x1][y1][x3][y2] + dp[x3][y1][x2][y2]); rep(y3, y1 + 1, y2) chmin(dp[x1][y1][x2][y2], dp[x1][y1][x2][y3] + dp[x1][y3][x2][y2]); dp[x1][y1][x2][y2] += a[x2][y2] + a[x1][y1] - a[x1][y2] - a[x2][y1]; } } } cout << dp[0][0][n][m] << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...