oj.uz

Submission #698115

# Submission time Handle Problem Language Result Execution time Memory
698115 2023-02-12T11:52:27 Z finn__ Jump (BOI06_jump) C++17
100 / 100
 2 ms 596 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 2 ms 596 KB Output is correct
20 Correct 2 ms 596 KB Output is correct