Submission #414066

#	Time	Username	Problem	Language	Result	Execution time	Memory
414066		SansPapyrus683	Raisins (IOI09_raisins)	C++17	100 / 100	546 ms	29352 KiB

raisins

#include <iostream>
#include <vector>
#include <algorithm>

using std::cout;
using std::endl;
using std::vector;

/**
 * https://oj.uz/problem/view/IOI09_raisins
 * 2 3 
 * 2 7 5 
 * 1 9 5 should output 77
 */
int main() {
    int row_num;
    int col_num;
    std::cin >> row_num >> col_num;
    vector<vector<int>> choco_prefs(row_num + 1, vector<int>(col_num + 1));
    for (int r = 1; r <= row_num; r++) {
        for (int c = 1; c <= col_num; c++) {
            std::cin >> choco_prefs[r][c];
            choco_prefs[r][c] += choco_prefs[r - 1][c]
                                 + choco_prefs[r][c - 1]
                                 - choco_prefs[r - 1][c - 1];
            
        }
    }
    auto sum = [&] (int rs, int cs, int re, int ce) {
        return choco_prefs[re + 1][ce + 1]
               - choco_prefs[rs][ce + 1]
               - choco_prefs[re + 1][cs]
               + choco_prefs[rs][cs];
    };

    vector<vector<vector<vector<int>>>> min_pay(
        row_num, vector<vector<vector<int>>>(
            col_num, vector<vector<int>>(row_num, vector<int>(col_num))
        )
    );
    for (int height = 1; height <= row_num; height++) {
        for (int width = 1; width <= col_num; width++) {
            if (height == 1 && width == 1) {
                continue;  // for a 1x1 block of chocolate the ans is always 0
            }
            for (int r = 0; r <= row_num - height; r++) {
                for (int c = 0; c <= col_num - width; c++) {
                    int& curr = min_pay[r][c][r + height - 1][c + width - 1];
                    curr = INT32_MAX;
                    int cost = sum(r, c, r + height - 1, c + width - 1);
                    for (int hor_split = 1; hor_split < width; hor_split++) {
                        curr = std::min(
                            curr,
                            cost
                            + min_pay[r][c][r + height - 1][c + hor_split - 1]
                            + min_pay[r][c + hor_split][r + height - 1][c + width - 1]
                        );
                    }
                    for (int vert_split = 1; vert_split < height; vert_split++) {
                        curr = std::min(
                            curr,
                            cost
                            + min_pay[r][c][r + vert_split - 1][c + width - 1]
                            + min_pay[r + vert_split][c][r + height - 1][c + width - 1]
                        );
                    }
                }
            }
        }
    }
    cout << min_pay[0][0][row_num - 1][col_num - 1] << endl;
}

• Subtask 1: 100 / 100