Submission #1194153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194153		SulA	Raisins (IOI09_raisins)	C++20	100 / 100	67 ms	34628 KiB

raisins

#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define popcount(x) __builtin_popcountll(x)
using namespace std;
using namespace chrono;

long long pref[51][51], dp[51][51][51][51];

void solve() {
    int n,m; cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> pref[i][j];
            dp[i][j][i][j] = pref[i][j];
            pref[i][j] += pref[i][j-1] + pref[i-1][j] - pref[i-1][j-1];
        }
    }
    for (int i = n; i >= 1; i--) for (int j = m; j >= 1; j--) for (int k = i; k <= n; k++) for (int l = j; l <= m; l++) {
        if (i == k && j == l) continue;
        dp[i][j][k][l] = 1e18;
        for (int split = i; split < k; split++)
            dp[i][j][k][l] = min(dp[i][j][k][l],
                                 dp[i][j][split][l] +
                                 dp[split+1][j][k][l]);
        for (int split = j; split < l; split++)
            dp[i][j][k][l] = min(dp[i][j][k][l],
                                 dp[i][split + 1][k][l] +
                                 dp[i][j][k][split]);
        dp[i][j][k][l] += pref[k][l] - pref[i-1][l] - pref[k][j-1] + pref[i-1][j-1];
//        printf("%d %d %d %d %d\n", i, j, k, l, dp[i][j][k][l]);
    }
    cout << dp[1][1][n][m] - pref[n][m];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

//    int t; cin >> t; while (t--)
        solve();
}

• Subtask 1: 100 / 100