#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
using namespace std;
using namespace __gnu_pbds;
#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int, int>>
#define vvi vector<vi>
#define vvii vector<vii>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define loop(_) for (int __ = 0; __ < (_); ++__)
#define forn(i, n) for (int i = 0; i < n; ++i)
#define pb push_back
#define f first
#define s second
#define sz(_) ((int)_.size())
#define all(_) _.begin(), _.end()
#define uni(_) unique(_)
#define lb lower_bound
#define ub upper_bound
#define si set<int>
#define ms multiset<int>
#define qi queue<int>
#define pq prioriry_queue<int>
#define mi map<int, int>
#define inc(i, l, r) for (int i = l; i <= r; i++)
#define dec(i, l, r) for (int i = l; i >= r; i--)
using lll = __int128;
using ll = long long;
using ld = long double;
const int N = 100 + 7;
const ll mod = 1e9 + 7;
const ll inf = 2e18;
auto ra = [] {char *p = new char ; delete p ; return ll(p) ; };
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count() * (ra() | 1));
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> os;
int n;
int a[N][N];
struct bigint
{
string ret;
bigint() { ret = "0"; }
bigint(string x) : ret(x) {}
bigint operator+=(bigint &ohs)
{
string now;
string s1 = ohs.ret;
int diff = max(sz(s1), sz(ret));
ret = string(diff - sz(ret), '0') + ret;
s1 = string(diff - sz(s1), '0') + s1;
reverse(all(ret)), reverse(all(s1));
int carry = 0;
for (int i = 0; i < sz(ret); ++i)
{
carry += s1[i] + ret[i] - 2 * '0';
now += char('0' + (carry % 10));
carry /= 10;
}
now += char('0' + carry);
int len = sz(now);
while (len && now[len - 1] == '0')
--len;
now = now.substr(0, len);
reverse(all(now));
ret = now;
if (sz(ret) == 0)
ret = "0";
return *this;
}
};
bigint dp[N][N];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifndef ONLINE_JUDGE
#endif
cin >> n;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
cin >> a[i][j];
dp[n - 1][n - 1] = bigint("1");
for (int i = n - 1; ~i; --i)
{
for (int j = n - 1; ~j; --j)
{
if (i == n - 1 && j == n - 1)
continue;
if (i + a[i][j] < n)
dp[i][j] += dp[i + a[i][j]][j];
if (j + a[i][j] < n)
dp[i][j] += dp[i][j + a[i][j]];
}
}
cout << dp[0][0].ret;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
748 KB |
Output is correct |
| 2 |
Correct |
1 ms |
748 KB |
Output is correct |
| 3 |
Correct |
1 ms |
748 KB |
Output is correct |
| 4 |
Correct |
1 ms |
748 KB |
Output is correct |
| 5 |
Correct |
1 ms |
748 KB |
Output is correct |
| 6 |
Correct |
1 ms |
748 KB |
Output is correct |
| 7 |
Correct |
1 ms |
748 KB |
Output is correct |
| 8 |
Correct |
1 ms |
748 KB |
Output is correct |
| 9 |
Correct |
1 ms |
748 KB |
Output is correct |
| 10 |
Correct |
1 ms |
748 KB |
Output is correct |
| 11 |
Correct |
1 ms |
748 KB |
Output is correct |
| 12 |
Correct |
1 ms |
748 KB |
Output is correct |
| 13 |
Correct |
1 ms |
748 KB |
Output is correct |
| 14 |
Correct |
2 ms |
748 KB |
Output is correct |
| 15 |
Correct |
4 ms |
748 KB |
Output is correct |
| 16 |
Correct |
7 ms |
1004 KB |
Output is correct |
| 17 |
Correct |
6 ms |
876 KB |
Output is correct |
| 18 |
Correct |
10 ms |
1004 KB |
Output is correct |
| 19 |
Correct |
8 ms |
876 KB |
Output is correct |
| 20 |
Correct |
13 ms |
1132 KB |
Output is correct |
