제출 #1033590

#제출 시각아이디문제언어결과실행 시간메모리
1033590trucmaiTrains (BOI24_trains)C++17
8 / 100
2004 ms7672 KiB
#include <bits/stdc++.h> #ifdef LOCAL #include "/home/trcmai/code/tools.h" #define debug(x...) \ cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << "\e[39m" << endl; #else #define debug(x...) #endif using namespace std; #define all(a) a.begin(), a.end() #define fi first #define se second #define ll long long #define endl '\n' const int N = 1e6 + 6, LOG = 27, MOD = 1e9 + 7; const ll INF = 1e18; int n; ll add(ll x, ll y) { return (x + y) % MOD; } ll sub(ll x, ll y) { return (x - y % MOD + MOD) % MOD; } ll mul(ll x, ll y) { return (x * y) % MOD; } void upd(ll& x, ll y) { x = add(x, y); } ll dp[N], d[N], x[N]; const int BS = 320; signed main() { cin.tie(0)->sync_with_stdio(0); auto solver = [&]() { cin >> n; for (int i = 1; i <= n; ++i) cin >> d[i] >> x[i]; dp[1] = 1; for (int i = 1; i <= n; ++i) { if (d[i] == 0) continue; if (x[i] <= BS) for (int j = i + d[i]; j <= min(int(i + x[i] * d[i]), n); j += d[i]) upd(dp[j], dp[i]); } vector<pair<ll, pair<ll, ll>>> v; for (ll i = 1; i <= n; i++) { for (pair<ll, pair<ll, ll>> j : v) if ((i - j.fi) % j.se.fi == 0 && (i - j.fi) / j.se.fi <= j.se.se) { upd(dp[i], dp[j.first]); } if (d[i] && x[i] > BS) v.push_back({ i, { d[i], x[i] } }); } ll res = 0; for (int i = 1; i <= n; ++i) { cerr << dp[i] << " \n"[i == n]; upd(res, dp[i]); } cout << res << endl; }; int t = 1; // cin>>t; while (t--) solver(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...