Submission #994562

#TimeUsernameProblemLanguageResultExecution timeMemory
994562pavementTrains (BOI24_trains)C++17
8 / 100
227 ms57824 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 + j * d[i]]; } } else { assert(d[i] <= LIM2); for (int j = 1; j <= num_stops; j++) { dp[i] += vec[d[i]][i % d[i]][vec[d[i]][i % d[i]].size() - j]; } } } dp[i]++; 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...