제출 #1033754

#제출 시각아이디문제언어결과실행 시간메모리
1033754_shr104Trains (BOI24_trains)C++14
21 / 100
2096 ms1628 KiB
#include <bits/stdc++.h> using namespace std; typedef 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 d[mxn], x[mxn], n; long long dp[mxn]; 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; vector<pair<ll,pair<ll,ll>>> v; for (ll i = 1; i <= n; i++) { cin >> d[i] >> x[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]) continue; if (x[i] <= block) { if (i+d[i] > n) continue; for (ll j = i+d[i]; j <= min(n, i+x[i]*d[i]); j += d[i]) {dp[j] += dp[i]; dp[j] %= mod;} } else v.pb({i,{d[i],x[i]}}); } long long 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...