oj.uz

Submission #703277

# Submission time Handle Problem Language Result Execution time Memory
703277 2023-02-26T20:59:26 Z finn__ Raisins (IOI09_raisins) C++17
100 / 100
 147 ms 24768 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")
#pragma GCC target("avx2")

#define N 50

unsigned dp[N][N][N][N], s[N][N];

int main()
{
    size_t n, m;
    cin >> n >> m;

    memset(dp, 255, sizeof dp);
    for (size_t i = 0; i < n; ++i)
        for (size_t j = 0; j < m; ++j)
            cin >> s[i][j], dp[i][i][j][j] = 0;

    for (size_t i = 0; i < n; ++i)
        for (size_t j = 1; j < m; ++j)
            s[i][j] += s[i][j - 1];
    for (size_t j = 0; j < m; ++j)
        for (size_t i = 1; i < n; ++i)
            s[i][j] += s[i - 1][j];

    for (size_t l1 = 1; l1 <= n; ++l1)
        for (size_t l2 = 1; l2 <= m; ++l2)
            for (size_t i = 0; i + l1 <= n; ++i)
                for (size_t j = 0; j + l2 <= m; ++j)
                {
                    if (l1 == 1 && l2 == 1)
                        continue;

                    size_t const i1 = i, i2 = i + l1 - 1,
                                 j1 = j, j2 = j + l2 - 1;

                    for (size_t i3 = i1 + 1; i3 <= i2; ++i3)
                        dp[i1][i2][j1][j2] =
                            min(dp[i1][i2][j1][j2],
                                dp[i1][i3 - 1][j1][j2] + dp[i3][i2][j1][j2]);
                    for (size_t j3 = j1 + 1; j3 <= j2; ++j3)
                        dp[i1][i2][j1][j2] =
                            min(dp[i1][i2][j1][j2],
                                dp[i1][i2][j1][j3 - 1] + dp[i1][i2][j3][j2]);

                    dp[i1][i2][j1][j2] += s[i2][j2];
                    if (i1)
                        dp[i1][i2][j1][j2] -= s[i1 - 1][j2];
                    if (j1)
                        dp[i1][i2][j1][j2] -= s[i2][j1 - 1];
                    if (i1 && j1)
                        dp[i1][i2][j1][j2] += s[i1 - 1][j1 - 1];
                }

    cout << dp[0][n - 1][0][m - 1] << '\n';
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 24660 KB Output is correct
2 Correct 10 ms 24740 KB Output is correct
3 Correct 9 ms 24660 KB Output is correct
4 Correct 10 ms 24696 KB Output is correct
5 Correct 9 ms 24660 KB Output is correct
6 Correct 9 ms 24660 KB Output is correct
7 Correct 9 ms 24660 KB Output is correct
8 Correct 10 ms 24672 KB Output is correct
9 Correct 10 ms 24660 KB Output is correct
10 Correct 12 ms 24684 KB Output is correct
11 Correct 11 ms 24660 KB Output is correct
12 Correct 22 ms 24768 KB Output is correct
13 Correct 25 ms 24768 KB Output is correct
14 Correct 12 ms 24724 KB Output is correct
15 Correct 25 ms 24660 KB Output is correct
16 Correct 10 ms 24728 KB Output is correct
17 Correct 16 ms 24764 KB Output is correct
18 Correct 56 ms 24660 KB Output is correct
19 Correct 121 ms 24660 KB Output is correct
20 Correct 147 ms 24660 KB Output is correct