Submission #489659

#	Time	Username	Problem	Language	Result	Execution time	Memory
489659		Alexandruabcde	Raisins (IOI09_raisins)	C++14	100 / 100	169 ms	37192 KiB

raisins

#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 55;
typedef long long LL;
constexpr LL INF = 1000000000000000000;

int N, M;

LL R[NMAX][NMAX];
LL dp[NMAX][NMAX][NMAX][NMAX];

LL SumArea (int A, int B, int C, int D) {
    return (R[C][D] - R[A-1][D] - R[C][B-1] + R[A-1][B-1]);
}

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;
    for (int i = 1; i <= N; ++ i )
        for (int j = 1; j <= M; ++ j ) {
            cin >> R[i][j];
            R[i][j] = (R[i][j] + R[i-1][j] + R[i][j-1] - R[i-1][j-1]);
        }
}

void Solve () {
    for (int Lgi = 1; Lgi <= N; ++ Lgi )
        for (int Lgj = 1; Lgj <= M; ++ Lgj ) {
            if (Lgi == 1 && Lgj == 1) continue;

            for (int i = 1; i + Lgi - 1 <= N; ++ i ) {
                for (int j = 1; j + Lgj - 1 <= M; ++ j ) {
                    LL area = SumArea(i, j, i + Lgi - 1, j + Lgj - 1);
                    int cap_dri = i + Lgi - 1, cap_drj = j + Lgj - 1;
                    dp[Lgi][Lgj][i][j] = INF;
                    for (int aux_i = i; aux_i < cap_dri; ++ aux_i )
                        dp[Lgi][Lgj][i][j] = min(dp[Lgi][Lgj][i][j], area + dp[aux_i-i+1][Lgj][i][j] + dp[cap_dri-aux_i][Lgj][aux_i+1][j]);

                    for (int aux_j = j; aux_j < cap_drj; ++ aux_j)
                        dp[Lgi][Lgj][i][j] = min(dp[Lgi][Lgj][i][j], area + dp[Lgi][aux_j-j+1][i][j] + dp[Lgi][cap_drj-aux_j][i][aux_j+1]);
                }
            }
        }

    cout << dp[N][M][1][1] << '\n';
}

int main () {
    Read();
    Solve();

    return 0;
}

• Subtask 1: 100 / 100