oj.uz

Submission #426537

# Submission time Handle Problem Language Result Execution time Memory
426537 2021-06-14T06:09:07 Z haxorman Raisins (IOI09_raisins) C++14
100 / 100
 522 ms 57664 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN = 52;
const long long INF = 1e18 + 7LL;

int n, m;
long long grid[mxN][mxN], pref[mxN][mxN], dp[mxN][mxN][mxN][mxN];

long long rec(int row_1, int col_1, int row_2, int col_2) {
    if (row_1 == row_2 && col_1 == col_2) {
        return 0;
    }

    if (dp[row_1][col_1][row_2][col_2] != -1) {
        return dp[row_1][col_1][row_2][col_2];
    }

    long long ret = INF;
    for (int j = col_1; j < col_2; ++j) {
        ret = min(ret, rec(row_1, col_1, row_2, j) +
                       rec(row_1, j + 1, row_2, col_2));
    }

    for (int i = row_1; i < row_2; ++i) {
        ret = min(ret, rec(row_1, col_1, i, col_2) +
                       rec(i + 1, col_1, row_2, col_2));
    }

    dp[row_1][col_1][row_2][col_2] = ret +
    pref[row_2][col_2] - pref[row_1 - 1][col_2] - pref[row_2][col_1 - 1] + pref[row_1 - 1][col_1 - 1];

    return dp[row_1][col_1][row_2][col_2];
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;

    memset(dp, -1, sizeof(dp));

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> grid[i][j];
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + grid[i][j];
        }
    }

    cout << rec(1, 1, n, m) << "\n";
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 57548 KB Output is correct
2 Correct 28 ms 57528 KB Output is correct
3 Correct 28 ms 57548 KB Output is correct
4 Correct 28 ms 57548 KB Output is correct
5 Correct 26 ms 57472 KB Output is correct
6 Correct 25 ms 57548 KB Output is correct
7 Correct 27 ms 57496 KB Output is correct
8 Correct 30 ms 57440 KB Output is correct
9 Correct 33 ms 57540 KB Output is correct
10 Correct 41 ms 57548 KB Output is correct
11 Correct 34 ms 57452 KB Output is correct
12 Correct 57 ms 57568 KB Output is correct
13 Correct 82 ms 57664 KB Output is correct
14 Correct 41 ms 57548 KB Output is correct
15 Correct 95 ms 57572 KB Output is correct
16 Correct 31 ms 57464 KB Output is correct
17 Correct 50 ms 57584 KB Output is correct
18 Correct 264 ms 57596 KB Output is correct
19 Correct 519 ms 57608 KB Output is correct
20 Correct 522 ms 57584 KB Output is correct