# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
221234 | tatyam | Raisins (IOI09_raisins) | C++17 | 315 ms | 25976 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |