제출 #1306520

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306520		Jer	Jump (BOI06_jump)	C++20	100 / 100	4 ms	1088 KiB

jump

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

string add(string a, string b)
{
    string res;
    int carry = 0;

    for (int i = 0; i < max(a.size(), b.size()); i++)
    {
        int one = (i >= a.size() ? 0 : a[a.size() - 1 - i] - '0');
        int two = (i >= b.size() ? 0 : b[b.size() - 1 - i] - '0');

        int sum = one + two + carry;
        res.push_back((sum % 10) + '0');
        carry = sum / 10;
    }

    if (carry)
        res.push_back(carry + '0');

    reverse(res.begin(), res.end());
    return res;
}

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

int n;

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

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

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

    return (dp[i][j] = add(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: 100 / 100