Submission #1214936

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214936		harvsftw	Raisins (IOI09_raisins)	C++20	10 / 100	153 ms	34568 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[N][N];
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[i][j];

            grid_sum[i][j] = grid[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];
            }
        }

        // F(j, m) {
        //     cout << grid_sum[i][j] << ' ';
        // }
        // cout << endl;
    }

    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];
                    }

                    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 " << h << ' ' << w << ' ' << r << ' ' << c << " = " << dp[h][w][r][c] << endl;
                }
            }
        }
    }

    cout << dp[n][m][0][0] << endl;
}

• Subtask 1: 10 / 100