oj.uz

Submission #989774

# Submission time Handle Problem Language Result Execution time Memory
989774 2024-05-28T18:50:01 Z aaaaaarroz Raisins (IOI09_raisins) C++17
100 / 100
 588 ms 29528 KB 
    #include <bits/stdc++.h>
     
    using namespace std;
    using vi = vector<int>;
    using vii = vector<vi>;
    using vi3 = vector<vii>;
    using vi4 = vector<vi3>;
     
    vii r, sum;
    vi4 dp;
     
    int value(int x1, int y1, int x2, int y2) {
        return sum[x2+1][y2+1] - sum[x1][y2+1] - sum[x2+1][y1] + sum[x1][y1];
    }
     
    int raisins(int x1, int y1, int x2, int y2) {
        if(dp[x1][y1][x2][y2] != -1) return dp[x1][y1][x2][y2];
     
        if (x1 == x2 && y1 == y2) return dp[x1][y1][x2][y2] = 0;
     
        dp[x1][y1][x2][y2] = 1e9;
        for (int x = x1; x < x2; ++x) {
            dp[x1][y1][x2][y2] = min(dp[x1][y1][x2][y2], raisins(x1, y1, x, y2) + raisins(x+1, y1, x2, y2) + value(x1, y1, x2, y2));
        }
        for (int y = y1; y < y2; ++y) {
            dp[x1][y1][x2][y2] = min(dp[x1][y1][x2][y2], raisins(x1, y1, x2, y) + raisins(x1, y+1, x2, y2) + value(x1, y1, x2, y2));
        }
     
        return dp[x1][y1][x2][y2];
    }
     
    int main() {
        int n, m;
        cin >> n >> m;
        r = vii (n, vi(m));
        sum = vii(n+1, vi(m+1, 0));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                cin >> r[i][j];
                sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] - sum[i][j] + r[i][j];
            }
        }
        dp = vi4(n, vi3(m, vii(n, vi(m, -1))));
        cout << raisins(0, 0, n-1, m-1) << '\n';
     
        return 0;
    }

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 7 ms 1508 KB Output is correct
9 Correct 12 ms 2020 KB Output is correct
10 Correct 18 ms 2624 KB Output is correct
11 Correct 15 ms 2140 KB Output is correct
12 Correct 58 ms 5852 KB Output is correct
13 Correct 86 ms 8280 KB Output is correct
14 Correct 25 ms 2904 KB Output is correct
15 Correct 119 ms 9564 KB Output is correct
16 Correct 10 ms 1880 KB Output is correct
17 Correct 46 ms 4700 KB Output is correct
18 Correct 311 ms 18636 KB Output is correct
19 Correct 478 ms 26716 KB Output is correct
20 Correct 588 ms 29528 KB Output is correct