oj.uz

Submission #489659

# Submission time Handle Problem Language Result Execution time Memory
489659 2021-11-23T15:50:37 Z Alexandruabcde Raisins (IOI09_raisins) C++14
100 / 100
 169 ms 37192 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 472 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 464 KB Output is correct
6 Correct 1 ms 976 KB Output is correct
7 Correct 2 ms 1104 KB Output is correct
8 Correct 4 ms 3520 KB Output is correct
9 Correct 6 ms 5072 KB Output is correct
10 Correct 8 ms 6096 KB Output is correct
11 Correct 5 ms 5072 KB Output is correct
12 Correct 13 ms 10960 KB Output is correct
13 Correct 23 ms 14408 KB Output is correct
14 Correct 6 ms 6420 KB Output is correct
15 Correct 26 ms 16272 KB Output is correct
16 Correct 5 ms 5584 KB Output is correct
17 Correct 14 ms 11728 KB Output is correct
18 Correct 87 ms 27568 KB Output is correct
19 Correct 169 ms 34008 KB Output is correct
20 Correct 161 ms 37192 KB Output is correct