Submission #1242105

#TimeUsernameProblemLanguageResultExecution timeMemory
1242105wedonttalkanymoreTrains (BOI24_trains)C++20
100 / 100
145 ms10124 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int long long #define pii pair<ll, ll> #define fi first #define se second const ll N = 2e5 + 5, mod = 1e9 + 7, block = 320; int n; int d[N], x[N]; int dp[N]; int total[block][block]; vector<int> adj[N]; signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) cin >> d[i] >> x[i]; dp[1] = 1; for (int i = 1; i <= n; i++) { for (int v : adj[i]) { int dv = d[v]; int rv = v % dv; total[dv][rv] = (total[dv][rv] - dp[v] + mod) % mod; } for (int b = 1; b < block; b++) { dp[i] = (dp[i] + total[b][i % b]) % mod; } if (d[i] == 0) continue; if (d[i] >= block) { for (int t = 1; t <= x[i]; t++) { int j = i + t * d[i]; if (j > n) break; dp[j] = (dp[j] + dp[i]) % mod; } } else { int idx = min(n + 1, i + (x[i] + 1) * d[i]); adj[idx].push_back(i); int r = i % d[i]; total[d[i]][r] = (total[d[i]][r] + dp[i]) % mod; } } int sum = 0; for (int i = 1; i <= n; i++) sum = (sum + dp[i]) % mod; cout << sum; return 0; }
#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...