제출 #394399

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
394399		iulia13	건포도 (IOI09_raisins)	C++14	70 / 100	656 ms	48908 KiB

raisins

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