oj.uz

Submission #858797

# Submission time Handle Problem Language Result Execution time Memory
858797 2023-10-09T08:06:12 Z aykhn Raisins (IOI09_raisins) C++14
100 / 100
 194 ms 68228 KB 
#include <bits/stdc++.h>

// author : aykhn

using namespace std;
typedef long long ll;

#define pb push_back
#define ins insert
#define mpr make_pair
#define all(v) v.begin(), v.end()
#define bpc __builtin_popcount
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define int ll
#define infll 0x3F3F3F3F3F3F3F3F
#define inf 0x3F3F3F3F

const int MXN = 55;

int n, m;
int dp[MXN][MXN][MXN][MXN];
int pref[MXN][MXN];
int a[MXN][MXN];

int sum(int i1, int j1, int i2, int j2)
{
    int x = pref[i1 - 1][j2];
    int y = pref[i2][j1 - 1];
    return pref[i2][j2] - x - y + pref[i1 - 1][j1 - 1];
}

int f(int i1, int j1, int i2, int j2)
{
    if (i1 == i2 && j1 == j2) return 0;
    if (dp[i1][j1][i2][j2] != -1) return dp[i1][j1][i2][j2];
    int res = inf;
    int id = -1;
    for (int k = j1; k < j2; k++)
    {
        int x = f(i1, j1, i2, k) + f(i1, k + 1, i2, j2);
        if (x < res)
        {
            id = k;
            res = x;
        }
    }
    for (int k = i1; k < i2; k++)
    {
        int x = f(i1, j1, k, j2) + f(k + 1, j1, i2, j2);
        if (x < res)
        {
            id = -k;
            res = x;
        }
    }
    return dp[i1][j1][i2][j2] = res + sum(i1, j1, i2, j2);
}

void _()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++) 
        {
            cin >> a[i][j];
            for (int k = 1; k <= n; k++)
            {
                for (int l = 1; l <= m; l++)
                {
                    dp[i][j][k][l] = -1;
                }
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + a[i][j];
        }
    }

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

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    //cin >> t;
    for (int i = 1; i <= t; i++)
    {
        _();
    }
}

Compilation message

raisins.cpp: In function 'll f(ll, ll, ll, ll)':
raisins.cpp:40:9: warning: variable 'id' set but not used [-Wunused-but-set-variable]
   40 |     int id = -1;
      |         ^~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 10592 KB Output is correct
6 Correct 2 ms 14820 KB Output is correct
7 Correct 2 ms 20836 KB Output is correct
8 Correct 5 ms 25104 KB Output is correct
9 Correct 7 ms 33116 KB Output is correct
10 Correct 8 ms 35376 KB Output is correct
11 Correct 7 ms 27164 KB Output is correct
12 Correct 19 ms 43360 KB Output is correct
13 Correct 31 ms 47460 KB Output is correct
14 Correct 10 ms 29028 KB Output is correct
15 Correct 36 ms 49760 KB Output is correct
16 Correct 8 ms 51808 KB Output is correct
17 Correct 18 ms 55904 KB Output is correct
18 Correct 83 ms 64096 KB Output is correct
19 Correct 148 ms 64092 KB Output is correct
20 Correct 194 ms 68228 KB Output is correct