oj.uz

Submission #312928

# Submission time Handle Problem Language Result Execution time Memory
312928 2020-10-14T17:26:39 Z fergonzgut21 Raisins (IOI09_raisins) C++14
100 / 100
 1000 ms 28152 KB 
#include <iostream>
#define MAX 53
using namespace std;

int N, M, A[MAX][MAX], B[MAX][MAX], DP[MAX][MAX][MAX][MAX];

int solve (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)
    {
        DP[x1][y1][x2][y2] = 0;
        return 0;
    }
    int res = 1073741822;
    int n1 = 0;
    int n2 = 0;
    for (int i = x1; i < x2; i++)
    {
        n1 = solve(x1,y1,i,y2);
        n2 = solve(i + 1,y1,x2,y2);
        if (n1 + n2 < res)
            res = n1 + n2;
    }
    for (int i = y1; i < y2; i++)
    {
        n1 = solve(x1,y1,x2,i);
        n2 = solve(x1,i + 1,x2,y2);
        if (n1 + n2 < res)
            res = n1 + n2;
    }
    res += B[x2][y2] - B[x1 - 1][y2] - B[x2][y1 - 1] + B[x1 - 1][y1 - 1];
    DP[x1][y1][x2][y2] = res;
    return res;
}

int main()
{
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
        {
            cin >> A[i][j];
            B[i][j] = A[i][j] + B[i - 1][j] + B[i][j - 1] - B[i - 1][j - 1];
        }
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            for (int k = 1; k <= N; k++)
                for (int l = 1; l <= M; l++)
                    DP[i][j][k][l] = -1;
    cout << solve (1, 1, N, M);
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 1024 KB Output is correct
7 Correct 2 ms 1152 KB Output is correct
8 Correct 13 ms 3456 KB Output is correct
9 Correct 22 ms 4992 KB Output is correct
10 Correct 32 ms 6016 KB Output is correct
11 Correct 30 ms 5116 KB Output is correct
12 Correct 99 ms 10880 KB Output is correct
13 Correct 168 ms 13824 KB Output is correct
14 Correct 43 ms 6272 KB Output is correct
15 Correct 209 ms 15096 KB Output is correct
16 Correct 18 ms 5120 KB Output is correct
17 Correct 87 ms 10112 KB Output is correct
18 Correct 536 ms 21752 KB Output is correct
19 Correct 857 ms 26488 KB Output is correct
20 Correct 1000 ms 28152 KB Output is correct