oj.uz

Submission #394399

# Submission time Handle Problem Language Result Execution time Memory
394399 2021-04-26T13:51:54 Z iulia13 Raisins (IOI09_raisins) C++14
70 / 100
 656 ms 48908 KB 
#include <iostream>

using namespace std;
const int C = 50;
int dp[C][C][C][C];
int a[C][C];
int main()
{
    int n, m, i, j, ii, jj;
    cin >> n >> m;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            a[i][j] += (a[i][j - 1] + a[i - 1][j] - a[i - 1][j - 1]);
            for (ii = 1; ii <= n; ii++)
                for (jj = 1; jj <= m; jj++)
                    dp[i][j][ii][jj] = 1e9;
        }
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            dp[i][j][i][j] = 0;
    for (int l = 1; l <= n + m - 2; l++)
        for (int x1 = 1; x1 <= n; x1++)
            for (int y1 = 1; y1 <= n; y1++)
                for (int x2 = x1; x2 <= n && x2 - x1 <= l; x2++)
                {
                    int y2 = y1 + (l - (x2 - x1));
                    int x = a[x2][y2] + a[x1 - 1][y1 - 1] - a[x1 - 1][y2] - a[x2][y1 - 1];
                    for (i = x1; i < x2; i++)
                        dp[x1][y1][x2][y2] = min(dp[x1][y1][x2][y2], dp[x1][y1][i][y2] + dp[i + 1][y1][x2][y2] + x);
                    for (i = y1; i < y2; i++)
                        dp[x1][y1][x2][y2] = min(dp[x1][y1][x2][y2], dp[x1][y1][x2][i] + dp[x1][i + 1][x2][y2] + x);
                }
    cout << dp[1][1][n][m];
    return 0;
}

Subtask #1
70.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Correct 1 ms 556 KB Output is correct
6 Correct 2 ms 844 KB Output is correct
7 Correct 3 ms 1704 KB Output is correct
8 Incorrect 7 ms 3416 KB Output isn't correct
9 Correct 19 ms 5192 KB Output is correct
10 Correct 24 ms 5840 KB Output is correct
11 Incorrect 14 ms 4880 KB Output isn't correct
12 Correct 78 ms 10256 KB Output is correct
13 Correct 128 ms 12356 KB Output is correct
14 Incorrect 18 ms 6092 KB Output isn't correct
15 Correct 186 ms 13796 KB Output is correct
16 Correct 101 ms 12888 KB Output is correct
17 Correct 218 ms 15884 KB Output is correct
18 Correct 656 ms 21588 KB Output is correct
19 Runtime error 297 ms 47428 KB Execution killed with signal 11
20 Runtime error 39 ms 48908 KB Execution killed with signal 11