제출 #1324061

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1324061		kasamchi	건포도 (IOI09_raisins)	C++20	100 / 100	140 ms	21120 KiB

raisins

#include <bits/stdc++.h>
using namespace std;

#define INF 1000000000

int pre[51][51];
int dp[51][51][51][51];

int solve(int u, int l, int d, int r) {
    if (dp[u][l][d][r] > 0) {
        return dp[u][l][d][r];
    }
    if (u == d && l == r) {
        return 0;
    }
    dp[u][l][d][r] = INF;
    for (int x = u; x < d; x++) {
        dp[u][l][d][r] = min(dp[u][l][d][r], solve(u, l, x, r) + solve(x + 1, l, d, r));
    }
    for (int y = l; y < r; y++) {
        dp[u][l][d][r] = min(dp[u][l][d][r], solve(u, l, d, y) + solve(u, y + 1, d, r));
    }
    dp[u][l][d][r] += pre[d][r] - pre[u - 1][r] - pre[d][l - 1] + pre[u - 1][l - 1];
    return dp[u][l][d][r];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N, M;
    cin >> N >> M;

    int v[51][51] = {};
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> v[i][j];
        }
    }

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            pre[i][j] = pre[i][j - 1] + v[i][j];
        }
        for (int j = 1; j <= M; j++) {
            pre[i][j] += pre[i - 1][j];
        }
    }

    cout << solve(1, 1, N, M) << '\n';
}

• Subtask 1: 100 / 100