제출 #1215707

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1215707		DippleThree	건포도 (IOI09_raisins)	C++20	100 / 100	127 ms	29508 KiB

raisins

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int r, c; cin >> r >> c;
    vector<vector<int>> grid(r, vector<int>(c));
    vector<vector<vector<vector<int>>>> dp(r, vector<vector<vector<int>>>(c, vector<vector<int>>(r, vector<int>(c, 1e8)))); // dp[dr][dc][sr][sc]
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> grid[i][j];
            dp[0][0][i][j] = 0;
        }
    }
    for (int i = 0; i < r; i++){
        for (int j = 1; j < c; j++){
            grid[i][j] += grid[i][j - 1];
        }
    }
    for (int i = 1; i < r; i++){
        for (int j = 0; j < c; j++){
            grid[i][j] += grid[i - 1][j];
        }
    }
    for (int dr = 0; dr < r; dr++){
        for (int dc = 0; dc < c; dc++){
            if (dr == 0 && dc == 0) continue;
            for (int sr = 0; sr + dr < r; sr++){
                for (int sc = 0; sc + dc < c; sc++){
                    int base = grid[sr + dr][sc + dc];
                    if (sr > 0) base -= grid[sr - 1][sc + dc];
                    if (sc > 0) base -= grid[sr + dr][sc - 1];
                    if (sr > 0 && sc > 0) base += grid[sr - 1][sc - 1];
                    for (int ddr = 1; ddr <= dr; ddr++){
                        dp[dr][dc][sr][sc] = min(dp[dr][dc][sr][sc], base + dp[ddr - 1][dc][sr][sc] + dp[dr - ddr][dc][sr + ddr][sc]);
                    }
                    for (int ddc = 1; ddc <= dc; ddc++){
                        dp[dr][dc][sr][sc] = min(dp[dr][dc][sr][sc], base + dp[dr][ddc - 1][sr][sc] + dp[dr][dc - ddc][sr][sc + ddc]);
                    }
                }
            }
        }
    }
    cout << dp[r - 1][c - 1][0][0] << "\n";
}

• Subtask 1: 100 / 100