Submission #1214938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214938		harvsftw	건포도 (IOI09_raisins)	C++20	100 / 100	79 ms	34628 KiB

raisins

#pragma GCC optimize("O3,inline")
#include <bits/stdc++.h>
using namespace std;

#define F(i, n) for(int i = 0; i < (n); i++)
#define FF(i, s, n) for(int i = s; i < (n); i++)
#define F_reverse(i, n) for(int i = (n) - 1; i >= 0; i--)
#define dcout if(0) cout
#define N 50 + 1

int64_t grid_sum[N][N];
int64_t dp[N][N][N][N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    F(i, n) {
        F(j, m) {
            cin >> grid_sum[i][j];
            if(j > 0) {
                grid_sum[i][j] += grid_sum[i][j - 1];
            }
        }
        if(i > 0) {
            F(j, m) {
                grid_sum[i][j] += grid_sum[i - 1][j];
            }
        }
    }

    FF(h, 1, n + 1) {
        FF(w, 1, m + 1) {
            if(h == 1 && w == 1) {
                continue;
            }
            F(r, n - h + 1) {
                F(c, m - w + 1) {
                    int64_t cost = grid_sum[r + h - 1][c + w - 1];
                    if(r > 0) {
                        cost -= grid_sum[r - 1][c + w - 1];
                    }
                    if(c > 0) {
                        cost -= grid_sum[r + h - 1][c - 1];
                    }
                    if(r > 0 && c > 0) {
                        cost += grid_sum[r - 1][c - 1];
                    }

                    int64_t subproblem_costs = INT64_MAX;
                    FF(split_width, 1, w) {
                        subproblem_costs = min(subproblem_costs, dp[h][split_width][r][c] + dp[h][w - split_width][r][c + split_width]);
                    }
                    FF(split_height, 1, h) {
                        subproblem_costs = min(subproblem_costs, dp[split_height][w][r][c] + dp[h - split_height][w][r + split_height][c]);
                    }

                    dp[h][w][r][c] = cost + subproblem_costs;
                }
            }
        }
    }

    cout << dp[n][m][0][0] << '\n';
}

• Subtask 1: 100 / 100