oj.uz

Submission #924802

# Submission time Handle Problem Language Result Execution time Memory
924802 2024-02-09T17:12:15 Z boris_mihov Raisins (IOI09_raisins) C++17
100 / 100
 428 ms 95692 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 4696 KB Output is correct
3 Correct 13 ms 10588 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 3 ms 19120 KB Output is correct
7 Correct 5 ms 27636 KB Output is correct
8 Correct 9 ms 34652 KB Output is correct
9 Correct 15 ms 45404 KB Output is correct
10 Correct 20 ms 47708 KB Output is correct
11 Correct 15 ms 37212 KB Output is correct
12 Correct 48 ms 59224 KB Output is correct
13 Correct 77 ms 66384 KB Output is correct
14 Correct 23 ms 39772 KB Output is correct
15 Correct 85 ms 70688 KB Output is correct
16 Correct 15 ms 69720 KB Output is correct
17 Correct 41 ms 75352 KB Output is correct
18 Correct 221 ms 89316 KB Output is correct
19 Correct 349 ms 93008 KB Output is correct
20 Correct 428 ms 95692 KB Output is correct