Submission #1033267

#TimeUsernameProblemLanguageResultExecution timeMemory
1033267borisAngelovTrains (BOI24_trains)C++17
37 / 100
189 ms3164 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 100005; const int mod = 1e9 + 7; int n; int d[maxn], x[maxn]; int dp[maxn]; int pref[maxn]; void fastIO() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } int main() { fastIO(); cin >> n; for (int i = 1; i <= n; ++i) { cin >> d[i] >> x[i]; } if (n <= 10000) { dp[1] = 1; int ans = 1; for (int i = 2; i <= n; ++i) { for (int j = i - 1; j >= 1; --j) { if (d[j] != 0 && (i - j) % d[j] == 0 && (i - j) / d[j] <= x[j]) { dp[i] += dp[j]; if (dp[i] >= mod) dp[i] -= mod; } } ans += dp[i]; if (ans >= mod) ans -= mod; } cout << ans << endl; return 0; } bool allD = true, allX = true; for (int i = 1; i <= n; ++i) { allD &= (d[i] == 1); allX &= (x[i] == 1000000000); } if (allD == true) { for (int i = 1; i <= n; ++i) { x[i] = min(x[i], n); } dp[1] = 1; pref[1] = 1; pref[x[1] + 2] = mod - 1; int ans = 1; for (int i = 2; i <= n; ++i) { pref[i] += pref[i - 1]; if (pref[i] >= mod) pref[i] -= mod; dp[i] = pref[i]; ans += dp[i]; if (ans >= mod) ans -= mod; pref[i + 1] += dp[i]; if (pref[i + 1] >= mod) pref[i + 1] -= mod; pref[min(n + 1, i + x[i] + 1)] -= dp[i]; if (pref[min(n + 1, i + x[i] + 1)] < 0) pref[min(n + 1, i + x[i] + 1)] += mod; //cout << i << " :: " << dp[i] << endl; //cout << min(n + 1, i + x[i] + 1) << endl; } cout << ans << endl; } return 0; } /* 5 1 3 1 1 1 2 1 2 1 2 2 :: 1 3 :: 2 4 :: 3 5 :: 5 */
#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...