oj.uz

Submission #771847

# Submission time Handle Problem Language Result Execution time Memory
771847 2023-07-03T10:29:06 Z BlockOG Raisins (IOI09_raisins) C++14
10 / 100
 124 ms 29384 KB 
#include <iostream>
#include <vector>
#include <utility>
#include <climits>

using namespace std;

/*
2 3
2 7 5
1 9 5

*/

int main() {
    int n, m; cin >> n >> m;

    vector<vector<int>> nums(n, vector<int>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> nums[i][j];

    vector<vector<int>> ps(n + 1, vector<int>(m + 1));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            ps[i + 1][j + 1] = nums[i][j] + ps[i + 1][j] + ps[i][j + 1] - ps[i][j];

    vector<vector<vector<vector<int>>>> dp(n, vector<vector<vector<int>>>(m, vector<vector<int>>(n, vector<int>(m))));
    for (int a = n - 1; a >= 0; a--) {
        for (int b = m - 1; b >= 0; b--) {
            for (int c = a; c < n; c++) {
                for (int d = b; d < m; d++) {
                    if (a == c && b == d) continue;

                    dp[a][b][c][d] = ps[n][m] + 100;
                    int raisins = ps[c + 1][d + 1] - ps[c + 1][b] - ps[a][d + 1] + ps[a][b];
                    for (int i = a; i < c; i++)
                        dp[a][b][c][d] = min(dp[a][b][c][d], raisins + dp[a][b][i][d] + dp[i + 1][b][c][d]);
                    for (int j = b; j < d; j++)
                        dp[a][b][c][d] = min(dp[a][b][c][d], raisins + dp[a][b][c][j] + dp[a][j + 1][c][d]);
                }
            }
        }
    }

    cout << dp[0][0][n - 1][m - 1];
}

Subtask #1
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Incorrect 1 ms 296 KB Output isn't correct
6 Incorrect 1 ms 340 KB Output isn't correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Incorrect 2 ms 1364 KB Output isn't correct
9 Incorrect 3 ms 1836 KB Output isn't correct
10 Incorrect 4 ms 2484 KB Output isn't correct
11 Incorrect 4 ms 2132 KB Output isn't correct
12 Incorrect 13 ms 5716 KB Output isn't correct
13 Incorrect 21 ms 8276 KB Output isn't correct
14 Incorrect 6 ms 2900 KB Output isn't correct
15 Incorrect 28 ms 9396 KB Output isn't correct
16 Incorrect 3 ms 1748 KB Output isn't correct
17 Incorrect 11 ms 4768 KB Output isn't correct
18 Incorrect 72 ms 18388 KB Output isn't correct
19 Incorrect 108 ms 26580 KB Output isn't correct
20 Incorrect 124 ms 29384 KB Output isn't correct