제출 #312928

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
312928		fergonzgut21	건포도 (IOI09_raisins)	C++14	100 / 100	1000 ms	28152 KiB

raisins

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