Submission #536226

#	Time	Username	Problem	Language	Result	Execution time	Memory
536226		timreizin	Raisins (IOI09_raisins)	C++17	100 / 100	609 ms	49264 KiB

raisins

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