Submission #858797

#	Time	Username	Problem	Language	Result	Execution time	Memory
858797		aykhn	Raisins (IOI09_raisins)	C++14	100 / 100	194 ms	68228 KiB

raisins

#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 (stderr)

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