Submission #1215356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215356		jer033	Raisins (IOI09_raisins)	C++20	100 / 100	289 ms	52780 KiB

raisins

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1'000'000'000'000'000;

ll total_sum[51][51][51][51];
ll dp[51][51][51][51];
ll arr[51][51];

int main()
{
    int N, M;
    cin >> N >> M;
    for (int i=0; i<N; i++)
        for (int j=0; j<M; j++)
        {
            cin >> arr[i][j];
            total_sum[i][i][j][j] = arr[i][j];
        }
    for (int diffi=0; diffi<N; diffi++)
        for (int diffj=0; diffj<M; diffj++)
        {
            for (int i=0; i<(N-diffi); i++)
                for (int j=0; j<(M-diffj); j++)
                {
                    int hi_i = i+diffi;
                    int hi_j = j+diffj;
                    ll total = 0;
                    ll ans = INF;
                    for (int cut_i = i; cut_i<hi_i; cut_i++)
                    {
                        total = total_sum[i][cut_i][j][hi_j] + total_sum[cut_i+1][hi_i][j][hi_j];
                        ans = min(ans, total + dp[i][cut_i][j][hi_j] + dp[cut_i+1][hi_i][j][hi_j]);
                    }
                    for (int cut_j = j; cut_j<hi_j; cut_j++)
                    {
                        total = total_sum[i][hi_i][j][cut_j] + total_sum[i][hi_i][cut_j+1][hi_j];
                        ans = min(ans, total + dp[i][hi_i][j][cut_j] + dp[i][hi_i][cut_j+1][hi_j]);
                    }
                    if ((i!=hi_i) or (j!=hi_j))
                    {
                        dp[i][hi_i][j][hi_j] = ans;
                        //cout << "dp " << i << ' ' << hi_i << ' ' << j << ' ' << hi_j << ' ' << ans << '\n';
                        total_sum[i][hi_i][j][hi_j] = total;
                    }
                }
        }
    cout << dp[0][N-1][0][M-1] << '\n';
}

• Subtask 1: 100 / 100