제출 #1312983

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

raisins

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

vector<vector<ll>> S, c;
vector<vector<vector<vector<ll>>>> DP;

ll TS(ll a, ll b, ll x, ll y){
    ll s = 0;
    for(ll i=a;i<=x;i++){
        s += S[i][y+1] - S[i][b];
    }
    return s;
}

ll calc(ll a, ll b, ll x, ll y){
    if(DP[a][b][x][y] != -1){return DP[a][b][x][y];}
    if(a==x and b==y){return DP[a][b][x][y] = 0;}
    ll mn = 125*1e8;
    for(ll i=b+1;i<=y;i++){
        mn = min(mn, calc(a, b, x, i-1) + calc(a, i, x, y));
    }
    for(ll i=a+1;i<=x;i++){
        mn = min(mn, calc(a, b, i-1, y) + calc(i, b, x, y));
    }
    return DP[a][b][x][y] = TS(a, b, x, y) + mn;
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    ll N, M;
    cin>>N>>M;
    c.resize(N, vector<ll>(M));
    S.resize(N, vector<ll>(M+1, 0));
    DP.resize(N, vector<vector<vector<ll>>>(M, vector<vector<ll>>(N, vector<ll>(M, -1))));
    for(ll i=0;i<N;i++){
        for(ll j=0;j<M;j++){
            S[i][j+1] = S[i][j];
            cin>>c[i][j];
            S[i][j+1] += c[i][j];
        }
    }
    cout<<calc(0, 0, N-1, M-1);
}

• Subtask 1: 100 / 100