Submission #337489

#TimeUsernameProblemLanguageResultExecution timeMemory
337489arborRaisins (IOI09_raisins)C++17
100 / 100
925 ms23020 KiB
#include <bits/stdc++.h> #define all(x) x.begin(), x.end() using namespace std; using ll = long long; using pii = pair<int, int>; const int MN = 55; int N, M, ps[MN][MN], dp[MN][MN][MN][MN]; int go(int x1, int y1, int x2, int y2) { int &ret = dp[x1][y1][x2][y2]; if (ret) return ret; if (x1 == x2 && y1 == y2) return 0; ret = 1e9; for (int nx = x1 + 1; nx <= x2; nx++) ret = min(ret, go(x1, y1, nx - 1, y2) + go(nx, y1, x2, y2)); for (int ny = y1 + 1; ny <= y2; ny++) ret = min(ret, go(x1, y1, x2, ny - 1) + go(x1, ny, x2, y2)); return ret += ps[x2][y2] - ps[x2][y1 - 1] - ps[x1 - 1][y2] + ps[x1 - 1][y1 - 1]; } int main() { ios_base::sync_with_stdio(0), cin.tie(0); cin >> N >> M; for (int i = 1; i <= N; i++) for (int j = 1; j <= M; j++) cin >> ps[i][j], ps[i][j] += ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1]; cout << go(1, 1, N, M) << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...