Submission #361253

#TimeUsernameProblemLanguageResultExecution timeMemory
361253mohamedsobhi777Jump (BOI06_jump)C++14
100 / 100
13 ms1132 KiB
#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 timeMemoryGrader output
Fetching results...