oj.uz

Submission #536226

# Submission time Handle Problem Language Result Execution time Memory
536226 2022-03-12T15:59:16 Z timreizin Raisins (IOI09_raisins) C++17
100 / 100
 609 ms 49264 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <array>

using namespace std;

using ll = long long;

ll solve(int x1, int x2, int y1, int y2, array<array<array<array<ll, 50>, 50>, 50>, 50> &dp, vector<vector<ll>> &pref)
{
    if (dp[x1][x2][y1][y2] != -1) return dp[x1][x2][y1][y2];
    if (x1 == x2 && y1 == y2) return dp[x1][x2][y1][y2] = 0;
    ll sum = pref[x2][y2];
    if (x1) sum -= pref[x1 - 1][y2];
    if (y1) sum -= pref[x2][y1 - 1];
    if (x1 && y1) sum += pref[x1 - 1][y1 - 1];
    ll minim = 1e18;
    for (int i = x1; i < x2; ++i) minim = min(minim, solve(x1, i, y1, y2, dp, pref) + solve(i + 1, x2, y1, y2, dp, pref));
    for (int i = y1; i < y2; ++i) minim = min(minim, solve(x1, x2, y1, i, dp, pref) + solve(x1, x2, i + 1, y2, dp, pref));
    return dp[x1][x2][y1][y2] = sum + minim;
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    vector<vector<ll>> r(n, vector<ll>(m));
    for (auto &i : r) for (ll &j : i) cin >> j;
    for (int i = 1; i < n; ++i) for (int j = 0; j < m; ++j) r[i][j] += r[i - 1][j];
    for (int i = 0; i < n; ++i) for (int j = 1; j < m; ++j) r[i][j] += r[i][j - 1];
    array<array<array<array<ll, 50>, 50>, 50>, 50> dp;
    for (int i = 0; i < 50; ++i) for (int j = 0; j < 50; ++j) for (int k = 0; k < 50; ++k) for (int l = 0; l < 50; ++l) dp[i][j][k][l] = -1;
    cout << solve(0, n - 1, 0, m - 1, dp, r);
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 49236 KB Output is correct
2 Correct 27 ms 49116 KB Output is correct
3 Correct 28 ms 49108 KB Output is correct
4 Correct 26 ms 49144 KB Output is correct
5 Correct 28 ms 49236 KB Output is correct
6 Correct 27 ms 49236 KB Output is correct
7 Correct 27 ms 49224 KB Output is correct
8 Correct 32 ms 49232 KB Output is correct
9 Correct 39 ms 49120 KB Output is correct
10 Correct 45 ms 49232 KB Output is correct
11 Correct 42 ms 49232 KB Output is correct
12 Correct 85 ms 49224 KB Output is correct
13 Correct 125 ms 49236 KB Output is correct
14 Correct 48 ms 49220 KB Output is correct
15 Correct 158 ms 49252 KB Output is correct
16 Correct 34 ms 49236 KB Output is correct
17 Correct 73 ms 49192 KB Output is correct
18 Correct 371 ms 49252 KB Output is correct
19 Correct 532 ms 49260 KB Output is correct
20 Correct 609 ms 49264 KB Output is correct