Submission #703277

#	Time	Username	Problem	Language	Result	Execution time	Memory
703277		finn__	Raisins (IOI09_raisins)	C++17	100 / 100	147 ms	24768 KiB

raisins

#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 / 100