oj.uz

Submission #698114

# Submission time Handle Problem Language Result Execution time Memory
698114 2023-02-12T11:51:12 Z finn__ Jump (BOI06_jump) C++17
65 / 100
 1000 ms 198732 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 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;
        }
    }
};

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
65.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 308 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 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 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 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Execution timed out 1076 ms 198732 KB Time limit exceeded
15 Execution timed out 1079 ms 192664 KB Time limit exceeded
16 Execution timed out 1078 ms 150396 KB Time limit exceeded
17 Execution timed out 1087 ms 154144 KB Time limit exceeded
18 Execution timed out 1091 ms 197672 KB Time limit exceeded
19 Execution timed out 1087 ms 195288 KB Time limit exceeded
20 Execution timed out 1082 ms 196960 KB Time limit exceeded