Submission #787028

#	Time	Username	Problem	Language	Result	Execution time	Memory
787028		Blagoj	Raisins (IOI09_raisins)	C++17	100 / 100	612 ms	35232 KiB

raisins

#include <bits/stdc++.h>

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) x.begin(), x.end()

ll mat[52][52], dp[52][52][52][52], prefSum[52][52];

ll calc(int x1, int y1, int x2, int y2) {
    x1--;
    y1--;
    return prefSum[x2][y2] - prefSum[x1][y2] - prefSum[x2][y1] + prefSum[x1][y1];
}

ll solve(int x1, int y1, int x2, int y2) {
    if (dp[x1][y1][x2][y2]) return dp[x1][y1][x2][y2];
    if (x1 == x2 && y1 == y2) return dp[x1][y1][x2][y2] = 0;
    ll ans = 10000000000;
    for (int i = x1; i < x2; i++) ans = min(ans, solve(x1, y1, i, y2) + solve(i + 1, y1, x2, y2) + calc(x1, y1, x2, y2));
    for (int j = y1; j < y2; j++) ans = min(ans, solve(x1, y1, x2, j) + solve(x1, j + 1, x2, y2) + calc(x1, y1, x2, y2));
    return dp[x1][y1][x2][y2] = ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        ll sum = 0;
        for (int j = 1; j <= m; j++) {
            cin >> mat[i][j];
            sum += mat[i][j];
            prefSum[i][j] = sum + prefSum[i - 1][j];
        }
    }
    cout << solve(1, 1, n, m);
}

• Subtask 1: 100 / 100