Submission #1214940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214940		harvsftw	건포도 (IOI09_raisins)	C++20	100 / 100	54 ms	21064 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

int32_t grid_sum[N][N];
int32_t dp[N][N][N][N];

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

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

    FF(i, 1, n + 1) {
        FF(j, 1, m + 1) {
            cin >> grid_sum[i][j];
            grid_sum[i][j] += grid_sum[i][j - 1];
        }
        FF(j, 1, m + 1) {
            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) {
                    int32_t cost = grid_sum[r + h][c + w];
                    cost -= grid_sum[r][c + w];
                    cost -= grid_sum[r + h][c];
                    cost += grid_sum[r][c];

                    int32_t subproblem_costs = INT32_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