제출 #994563

#제출 시각아이디문제언어결과실행 시간메모리
994563pavementTrains (BOI24_trains)C++17
21 / 100
2096 ms86992 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back const int MOD = (int)1e9 + 7, LIM = 200, LIM2 = 200; int N, d[100005], x[100005], dp[100005]; vector<int> vec[LIM2 + 5][LIM2]; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> N; for (int i = 1; i <= N; i++) { cin >> d[i] >> x[i]; } for (int i = N; i >= 1; i--) { if (d[i]) { int num_stops = min(x[i], (N - i) / d[i]); if (num_stops <= LIM) { for (int j = 1; j <= num_stops; j++) { dp[i] = (dp[i] + dp[i + j * d[i]]) % MOD; } } else { assert(d[i] <= LIM2); for (int j = 1; j <= num_stops; j++) { dp[i] = (dp[i] + vec[d[i]][i % d[i]][vec[d[i]][i % d[i]].size() - j]) % MOD; } } } dp[i] = (dp[i] + 1) % MOD; for (int j = 1; j <= LIM2; j++) { vec[j][i % j].pb(dp[i]); } } cout << dp[1] << '\n'; }
#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...