제출 #1033614

#제출 시각아이디문제언어결과실행 시간메모리
1033614_shr104Trains (BOI24_trains)C++14
8 / 100
2029 ms3404 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef long double ld; #define pb push_back #define pf push_front #define fi first #define se second const ll mod = 1e9+7, mxn = 1e5+7, block = 320; ll dp[mxn], d[mxn], x[mxn], n; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("test.inp","r",stdin); freopen("test.out","w",stdout); freopen("test.err","w",stderr); ll n; cin >> n; dp[1] = 1; for (ll i = 1; i <= n; i++) { cin >> d[i] >> x[i]; if (d[i] && x[i] <= block) { for (ll j = i+d[i]; j <= min(n, i+x[i]*d[i]); j += d[i]) {dp[j] += dp[i]; dp[j] %= mod;} } } 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) {dp[i] += dp[j.fi]; dp[i] %= mod;} if (d[i] && x[i] > block) v.pb({i,{d[i],x[i]}}); } ll ans = 0; for (ll i = 1; i <= n; i++) {ans += dp[i]; ans %= mod;} cout << ans; }
#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...