답안 #361251

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
361251 2021-01-28T23:56:42 Z mohamedsobhi777 Jump (BOI06_jump) C++14
95 / 100
13 ms 1132 KB
#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;
              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;
}
# 결과 실행 시간 메모리 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 Incorrect 1 ms 748 KB Output isn't 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 3 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 10 ms 1024 KB Output is correct
20 Correct 13 ms 1132 KB Output is correct