Submission #1306514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306514		Jer	Jump (BOI06_jump)	C++20	70 / 100	2 ms	584 KiB

jump

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 105;
int g[MAXN][MAXN];
ll dp[MAXN][MAXN];

int n;

bool inside(int i, int j) { return (i >= 0 and j >= 0 and i < n and j < n); }

ll calc(int i, int j)
{
    if (!inside(i, j))
        return 0;

    if (dp[i][j] != -1)
        return dp[i][j];

    return (dp[i][j] = calc(i + g[i][j], j) + calc(i, j + g[i][j]));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> g[i][j], dp[i][j] = (g[i][j] == 0 ? 0 : -1);

    dp[n - 1][n - 1] = 1;

    cout << calc(0, 0) << '\n';

    return 0;
}

• Subtask 1: 70 / 100