제출 #1025410

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1025410		HappyCapybara	건포도 (IOI09_raisins)	C++17	100 / 100	490 ms	29492 KiB

raisins

#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> ps;
vector<vector<vector<vector<int>>>> dp;

int val(int a, int b, int c, int d){
    return ps[b+1][d+1]-ps[a][d+1]-ps[b+1][c]+ps[a][c];
}

int solve(int a, int b, int c, int d){
    if (a == b && c == d) return 0;
    if (dp[a][b][c][d] != -1) return dp[a][b][c][d];
    int bsf = pow(10, 8);
    for (int i=a; i<b; i++) bsf = min(bsf, solve(a, i, c, d)+solve(i+1, b, c, d));
    for (int i=c; i<d; i++) bsf = min(bsf, solve(a, b, c, i)+solve(a, b, i+1, d));
    return dp[a][b][c][d] = bsf+val(a, b, c, d);
}

int main(){
    int n, m;
    cin >> n >> m;
    ps.resize(n+1, vector<int>(m+1, 0));
    for (int i=0; i<n; i++){
        for (int j=0; j<m; j++){
            cin >> ps[i+1][j+1];
            ps[i+1][j+1] += (ps[i][j+1]+ps[i+1][j]-ps[i][j]);
        }
    }
    dp.resize(n, vector<vector<vector<int>>>(n, vector<vector<int>>(m, vector<int>(m, -1))));
    cout << solve(0, n-1, 0, m-1) << "\n";
}

• Subtask 1: 100 / 100