oj.uz

Submission #507596

# Submission time Handle Problem Language Result Execution time Memory
507596 2022-01-12T19:17:30 Z tabr Raisins (IOI09_raisins) C++17
100 / 100
 189 ms 31996 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int h, w;
    cin >> h >> w;
    vector<vector<int>> a(h, vector<int>(w));
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> a[i][j];
        }
    }
    vector<vector<int>> pref(h + 1, vector<int>(w + 1));
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            pref[i + 1][j + 1] = pref[i + 1][j] + pref[i][j + 1] - pref[i][j] + a[i][j];
        }
    }
    const int inf = (int) 1e9;
    vector dp(h, vector(h + 1, vector(w, vector<int>(w + 1, inf))));
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            dp[i][i + 1][j][j + 1] = 0;
        }
    }
    for (int i1 = h - 1; i1 >= 0; i1--) {
        for (int i2 = i1 + 1; i2 <= h; i2++) {
            for (int j1 = w - 1; j1 >= 0; j1--) {
                for (int j2 = j1 + 1; j2 <= w; j2++) {
                    int sum = pref[i2][j2] - pref[i1][j2] - pref[i2][j1] + pref[i1][j1];
                    for (int i = i1 + 1; i < i2; i++) {
                        dp[i1][i2][j1][j2] = min(dp[i1][i2][j1][j2], dp[i1][i][j1][j2] + dp[i][i2][j1][j2] + sum);
                    }
                    for (int j = j1 + 1; j < j2; j++) {
                        dp[i1][i2][j1][j2] = min(dp[i1][i2][j1][j2], dp[i1][i2][j1][j] + dp[i1][i2][j][j2] + sum);
                    }
                }
            }
        }
    }
    cout << dp[0][h][0][w] << '\n';
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 292 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 3 ms 1356 KB Output is correct
9 Correct 5 ms 2124 KB Output is correct
10 Correct 7 ms 2588 KB Output is correct
11 Correct 5 ms 2124 KB Output is correct
12 Correct 17 ms 5836 KB Output is correct
13 Correct 28 ms 8524 KB Output is correct
14 Correct 8 ms 3276 KB Output is correct
15 Correct 33 ms 9676 KB Output is correct
16 Correct 4 ms 1868 KB Output is correct
17 Correct 15 ms 4940 KB Output is correct
18 Correct 106 ms 18888 KB Output is correct
19 Correct 144 ms 27120 KB Output is correct
20 Correct 189 ms 31996 KB Output is correct