oj.uz

Submission #840474

# Submission time Handle Problem Language Result Execution time Memory
840474 2023-08-31T12:05:46 Z overwatch9 Raisins (IOI09_raisins) C++17
30 / 100
 141 ms 25952 KB 
#include <iostream>
#include <vector>
using namespace std;
vector <vector <int>> grid;
vector <vector <int>> pfx;
const int maxn = 50 + 1;
int dp[maxn][maxn][maxn][maxn];
int solve(int r1, int r2, int c1, int c2) {
    if (r1 == r2 && c1 == c2)
        return 0;
    if (dp[r1][r2][c1][c2] != -1)
        return dp[r1][r2][c1][c2];
    int ans = 1e9;
    int x = pfx[r2][c2] - pfx[r2][c1-1] - pfx[r1-1][c2] + pfx[r2-1][c1-1];
    for (int i = r1; i < r2; i++) {
        ans = min(ans, solve(r1, i, c1, c2) + solve(i+1, r2, c1, c2) + x);
    }
    for (int i = c1; i < c2; i++) {
        ans = min(ans, solve(r1, r2, c1, i) + solve(r1, r2, i+1, c2) + x);
    }
    dp[r1][r2][c1][c2] = ans;
    return ans;
}
int main() {
    int n, m;
    cin >> n >> m;
    grid = pfx = vector <vector <int>> (n+1, vector <int> (m+1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            cin >> grid[i][j];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int l = 1; l <= m; l++) {
                for (int k = 1; k <= m; k++)
                    dp[i][j][l][k] = -1;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            pfx[i][j] = grid[i][j];
            pfx[i][j] += pfx[i-1][j] + pfx[i][j-1] - pfx[i-1][j-1];
        }
    }

    cout << solve(1, n, 1, m) << '\n';
}

Subtask #1
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Correct 0 ms 340 KB Output is correct
5 Incorrect 1 ms 516 KB Output isn't correct
6 Correct 1 ms 852 KB Output is correct
7 Incorrect 1 ms 1492 KB Output isn't correct
8 Incorrect 3 ms 3028 KB Output isn't correct
9 Incorrect 5 ms 5076 KB Output isn't correct
10 Incorrect 6 ms 5844 KB Output isn't correct
11 Incorrect 5 ms 4180 KB Output isn't correct
12 Correct 24 ms 10580 KB Output is correct
13 Incorrect 26 ms 12756 KB Output isn't correct
14 Incorrect 8 ms 4820 KB Output isn't correct
15 Incorrect 32 ms 14292 KB Output isn't correct
16 Incorrect 6 ms 9428 KB Output isn't correct
17 Incorrect 16 ms 14548 KB Output isn't correct
18 Incorrect 87 ms 22888 KB Output isn't correct
19 Correct 121 ms 23892 KB Output is correct
20 Incorrect 141 ms 25952 KB Output isn't correct