Submission #698115

#	Time	Username	Problem	Language	Result	Execution time	Memory
698115		finn__	Jump (BOI06_jump)	C++17	100 / 100	2 ms	596 KiB

jump

#include <bits/stdc++.h>
using namespace std;

template <size_t S>
struct BigInt
{
    array<uint64_t, S> digits;
    uint64_t const m = 1000000000000000000;

    BigInt() { fill(digits.begin(), digits.end(), 0); }

    BigInt<S> operator+(BigInt<S> const &x) const
    {
        BigInt<S> y;
        uint64_t carry = 0;
        for (size_t i = S - 1; i < S; i--)
        {
            y.digits[i] = (digits[i] + x.digits[i] + carry) % m;
            carry = (digits[i] + x.digits[i] + carry) / m;
        }
        return y;
    }

    void operator=(BigInt const &y)
    {
        copy(y.digits.begin(), y.digits.end(), digits.begin());
    }

    void operator=(uint64_t const &y)
    {
        fill(digits.begin(), digits.end(), 0);
        digits.back() = y;
    }

    void print() const
    {
        size_t i = 0;
        while (i + 1 < S && !digits[i])
            i++;
        cout << digits[i];
        i++;
        while (i < S)
        {
            string s = to_string(digits[i]);
            size_t const n = s.size();
            s.resize(18);
            copy(s.begin(), s.begin() + n, s.begin() + 18 - n);
            fill(s.begin(), s.begin() + 18 - n, '0');
            cout << s;
            i++;
        }
    }
};

int main()
{
    size_t n;
    cin >> n;

    vector<vector<BigInt<4>>> dp(n, vector<BigInt<4>>(n));
    dp[0][0] = 1;

    for (size_t i = 0; i < n; i++)
        for (size_t j = 0; j < n; j++)
        {
            unsigned u;
            cin >> u;
            if (u && i + u < n)
                dp[i + u][j] = dp[i + u][j] + dp[i][j];
            if (u && j + u < n)
                dp[i][j + u] = dp[i][j + u] + dp[i][j];
        }

    dp[n - 1][n - 1].print();
    cout << '\n';
}

• Subtask 1: 100 / 100