# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
564171 | SSRS | Jump (BOI06_jump) | C++14 | 7 ms | 1620 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;
struct bigint{
vector<int> d;
bigint(){
}
bigint(int x){
while (x > 0){
d.push_back(x % 10);
x /= 10;
}
if (d.empty()){
d.push_back(0);
}
}
int operator [](int k){
return d[k];
}
int size(){
return d.size();
}
};
ostream& operator <<(ostream& os, bigint x){
int N = x.size();
for (int i = N - 1; i >= 0; i--){
os << x[i];
}
return os;
}
bigint operator +(bigint A, bigint B){
int N1 = A.size();
int N2 = B.size();
int N = max(N1, N2) + 1;
bigint C;
C.d = vector<int>(N, 0);
for (int i = 0; i < N1; i++){
C.d[i] += A[i];
}
for (int i = 0; i < N2; i++){
C.d[i] += B[i];
}
for (int i = 0; i < N - 1; i++){
if (C[i] >= 10){
C.d[i + 1]++;
C.d[i] -= 10;
}
}
if (C.size() >= 2 && C[N - 1] == 0){
C.d.pop_back();
}
return C;
}
int main(){
int n;
cin >> n;
vector<vector<int>> A(n, vector<int>(n));
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
cin >> A[i][j];
}
}
vector<vector<bigint>> dp(n, vector<bigint>(n, 0));
dp[0][0] = 1;
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
if (i + A[i][j] < n){
dp[i + A[i][j]][j] = dp[i + A[i][j]][j] + dp[i][j];
}
if (j + A[i][j] < n){
dp[i][j + A[i][j]] = dp[i][j + A[i][j]] + dp[i][j];
};
}
}
cout << dp[n - 1][n - 1] << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |