Submission #698114

#TimeUsernameProblemLanguageResultExecution timeMemory
698114finn__Jump (BOI06_jump)C++17
65 / 100
1091 ms198732 KiB
#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'; }
#Verdict Execution timeMemoryGrader output
Fetching results...