Submission #1126769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126769		brianhdzmdo	Raisins (IOI09_raisins)	C++20	100 / 100	633 ms	29504 KiB

raisins

#include <iostream>
#include <vector>
#include <climits>

using namespace std;


int getSum(const vector<vector<int>>& prefixSum, int x1, int y1, int x2, int y2) {
    int total = prefixSum[x2 + 1][y2 + 1];
    if (x1 > 0) total -= prefixSum[x1][y2 + 1];
    if (y1 > 0) total -= prefixSum[x2 + 1][y1];
    if (x1 > 0 && y1 > 0) total += prefixSum[x1][y1];
    return total;
}

int dp(int x1, int y1, int x2, int y2, vector<vector<vector<vector<int>>>>& memo, const vector<vector<int>>& prefixSum) {
   
    if (x1 == x2 && y1 == y2) return 0;

  
    if (memo[x1][y1][x2][y2] != -1) return memo[x1][y1][x2][y2];

    int totalCost = getSum(prefixSum, x1, y1, x2, y2);
    int minCost = INT_MAX;

    
    for (int row = x1; row < x2; ++row) {
        int topCost = dp(x1, y1, row, y2, memo, prefixSum);
        int bottomCost = dp(row + 1, y1, x2, y2, memo, prefixSum);
        minCost = min(minCost, topCost + bottomCost);
    }

    
    for (int col = y1; col < y2; ++col) {
        int leftCost = dp(x1, y1, x2, col, memo, prefixSum);
        int rightCost = dp(x1, col + 1, x2, y2, memo, prefixSum);
        minCost = min(minCost, leftCost + rightCost);
    }

   
    return memo[x1][y1][x2][y2] = totalCost + minCost;
}

int main() {

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

    vector<vector<int>> chocolate(N, vector<int>(M));

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            cin >> chocolate[i][j];
        }
    }

   
    vector<vector<int>> prefixSum(N + 1, vector<int>(M + 1, 0));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            prefixSum[i + 1][j + 1] = chocolate[i][j] + prefixSum[i][j + 1] + prefixSum[i + 1][j] - prefixSum[i][j];
        }
    }

    
    vector<vector<vector<vector<int>>>> memo(N, vector<vector<vector<int>>>(M, vector<vector<int>>(N, vector<int>(M, -1))));

    
    cout << dp(0, 0, N - 1, M - 1, memo, prefixSum) << endl;

    return 0;
}

• Subtask 1: 100 / 100