oj.uz

Submission #787028

# Submission time Handle Problem Language Result Execution time Memory
787028 2023-07-18T16:42:02 Z Blagoj Raisins (IOI09_raisins) C++17
100 / 100
 612 ms 35232 KB 
#include <bits/stdc++.h>

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) x.begin(), x.end()

ll mat[52][52], dp[52][52][52][52], prefSum[52][52];

ll calc(int x1, int y1, int x2, int y2) {
    x1--;
    y1--;
    return prefSum[x2][y2] - prefSum[x1][y2] - prefSum[x2][y1] + prefSum[x1][y1];
}

ll solve(int x1, int y1, int x2, int y2) {
    if (dp[x1][y1][x2][y2]) return dp[x1][y1][x2][y2];
    if (x1 == x2 && y1 == y2) return dp[x1][y1][x2][y2] = 0;
    ll ans = 10000000000;
    for (int i = x1; i < x2; i++) ans = min(ans, solve(x1, y1, i, y2) + solve(i + 1, y1, x2, y2) + calc(x1, y1, x2, y2));
    for (int j = y1; j < y2; j++) ans = min(ans, solve(x1, y1, x2, j) + solve(x1, j + 1, x2, y2) + calc(x1, y1, x2, y2));
    return dp[x1][y1][x2][y2] = ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        ll sum = 0;
        for (int j = 1; j <= m; j++) {
            cin >> mat[i][j];
            sum += mat[i][j];
            prefSum[i][j] = sum + prefSum[i - 1][j];
        }
    }
    cout << solve(1, 1, n, m);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 276 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 456 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 8 ms 3412 KB Output is correct
9 Correct 14 ms 4948 KB Output is correct
10 Correct 19 ms 5976 KB Output is correct
11 Correct 16 ms 4948 KB Output is correct
12 Correct 56 ms 10700 KB Output is correct
13 Correct 107 ms 13816 KB Output is correct
14 Correct 26 ms 6084 KB Output is correct
15 Correct 121 ms 15724 KB Output is correct
16 Correct 11 ms 5332 KB Output is correct
17 Correct 46 ms 11328 KB Output is correct
18 Correct 282 ms 26188 KB Output is correct
19 Correct 491 ms 32412 KB Output is correct
20 Correct 612 ms 35232 KB Output is correct