# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
698114 | finn__ | Jump (BOI06_jump) | C++17 | 1091 ms | 198732 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |