Submission #520228

#	Time	Username	Problem	Language	Result	Execution time	Memory
520228		fergonzgut21	Raisins (IOI09_raisins)	C++14	100 / 100	769 ms	21008 KiB

raisins

#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 / 100