oj.uz

Submission #520228

# Submission time Handle Problem Language Result Execution time Memory
520228 2022-01-28T23:15:34 Z fergonzgut21 Raisins (IOI09_raisins) C++14
100 / 100
 769 ms 21008 KB 
#include <iostream>
#define MAX 51
using namespace std;

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

int solve (short int i1, short int j1, short int i2, short int j2)
{
    //cout << i1 << " " << j1 << " " << i2 << " " << j2 << endl;
    if (i1 == i2 && j1 == j2)
        return 0;
    if (B[i1][j1][i2][j2] > 0)
        return B[i1][j1][i2][j2];
    int res = 1000000000;
    for (int i = i1; i < i2; i++)
    {
        res = min (res, (solve(i1, j1, i, j2) + solve(i + 1, j1, i2, j2)));
    }
    for (int j = j1; j < j2; j++)
    {
        res = min (res, (solve(i1, j1, i2, j) + solve(i1, j + 1, i2, j2)));
    }
    B[i1][j1][i2][j2] = res + C[i2][j2] - C[i1-1][j2] - C[i2][j1-1] + C[i1-1][j1-1];
    return B[i1][j1][i2][j2];
}

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

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 844 KB Output is correct
8 Correct 10 ms 2636 KB Output is correct
9 Correct 17 ms 3604 KB Output is correct
10 Correct 25 ms 4212 KB Output is correct
11 Correct 21 ms 3716 KB Output is correct
12 Correct 78 ms 7324 KB Output is correct
13 Correct 134 ms 9380 KB Output is correct
14 Correct 44 ms 4608 KB Output is correct
15 Correct 159 ms 10268 KB Output is correct
16 Correct 20 ms 3604 KB Output is correct
17 Correct 64 ms 7176 KB Output is correct
18 Correct 425 ms 16008 KB Output is correct
19 Correct 631 ms 19528 KB Output is correct
20 Correct 769 ms 21008 KB Output is correct