Submission #1243825

#TimeUsernameProblemLanguageResultExecution timeMemory
1243825lopkusTrains (BOI24_trains)C++20
42 / 100
300 ms225864 KiB
#include <bits/stdc++.h> #define int long long int mod = 1e9 + 7; int add(int x, int y) { x += y; x %= mod; return x; } int S = 280; const int N = 1e5 + 5; signed main() { int n; std::cin >> n; std::vector<int> d(n + 1), x(n + 1); for(int i = 1; i <= n; i++) { std::cin >> d[i] >> x[i]; } std::vector<int> dp(n + 1, 0); dp[1] = 1; std::vector<std::vector<int>> pref(n + 1, std::vector<int>(S)); for(int i = 1; i <= n; i++) { if(d[i] == 0) { continue; } int e = (n - i + 1) / d[i]; for(int t = 1; t < S; t++) { if(i - t >= 0) { pref[i][t] = add(pref[i][t], pref[i - t][t]); dp[i] = add(dp[i], pref[i][t]); } } if(d[i] >= S) { for(int t = 1; t <= x[i] && i + t * d[i] <= n; t++) { dp[i + t * d[i]] = add(dp[i + t * d[i]], dp[i]); } } else { if(e <= S) { for(int t = 1; t <= x[i] && i + t * d[i] <= n; t++) { dp[i + t * d[i]] = add(dp[i + t * d[i]], dp[i]); } } else { pref[i][d[i]] = add(pref[i][d[i]], dp[i]); } } } int ans = 0; for(int i = 1; i <= n; i++) { ans = add(ans, dp[i]); } std::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...