제출 #924802

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
924802		boris_mihov	건포도 (IOI09_raisins)	C++17	100 / 100	428 ms	95692 KiB

raisins

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
#include <set>

typedef long long llong;
const int MAXN = 50 + 10;
const int INF  = 2e9;

int n, m, p;
int a[MAXN][MAXN];
int prefix[MAXN][MAXN];
llong dp[MAXN][MAXN][MAXN][MAXN];
bool bl[MAXN][MAXN][MAXN][MAXN];

llong f(int rowS, int colS, int rowE, int colE)
{
    if (rowS == rowE && colS == colE)
    {
        return 0;
    }

    if (bl[rowS][colS][rowE][colE])
    {
        return dp[rowS][colS][rowE][colE];
    }

    bl[rowS][colS][rowE][colE] = true;
    dp[rowS][colS][rowE][colE] = INF;
    int sum = prefix[rowE][colE] - prefix[rowS - 1][colE] - prefix[rowE][colS - 1] + prefix[rowS - 1][colS - 1];

    for (int at = rowS ; at < rowE ; ++at)
    {
        dp[rowS][colS][rowE][colE] = std::min(dp[rowS][colS][rowE][colE], f(rowS, colS, at, colE) + f(at + 1, colS, rowE, colE) + sum);
    }

    for (int at = colS ; at < colE ; ++at)
    {
        dp[rowS][colS][rowE][colE] = std::min(dp[rowS][colS][rowE][colE], f(rowS, colS, rowE, at) + f(rowS, at + 1, rowE, colE) + sum);
    }
    
    return dp[rowS][colS][rowE][colE];
}

void solve()
{
    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = 1 ; j <= m ; ++j)
        {
            prefix[i][j] = a[i][j] + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1];
        }
    }

    std::cout << f(1, 1, n, m) << '\n';
}

void input()
{
    std::cin >> n >> m;
    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = 1 ; j <= m ; ++j)
        {
            std::cin >> a[i][j];
        }
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}   

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

• Subtask 1: 100 / 100