Submission #1243835

#TimeUsernameProblemLanguageResultExecution timeMemory
1243835lopkusTrains (BOI24_trains)C++20
58 / 100
192 ms225828 KiB
#include <bits/stdc++.h> #define int long long int mod = 1e9 + 7; int add(int x, int y) { x += y; if(x < 0) { x += mod; } if(x >= mod) { 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 + 2, 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 { int w = std::min(n, i + x[i] * d[i]); pref[i][d[i]] = add(pref[i][d[i]], dp[i]); if(w + d[i] <= n) { pref[w + d[i]][d[i]] = add(pref[w + d[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...