Submission #1097223

#TimeUsernameProblemLanguageResultExecution timeMemory
1097223duckindogTrains (BOI24_trains)C++17
16 / 100
107 ms6704 KiB
#include <bits/stdc++.h> using namespace std; const int N = 100'000 + 10, M = 1'000'000'007, S = 400; int n; int d[N], x[N]; void add(int& x, const int& y) { x += y; if (x >= M) x -= M; }; vector<tuple<int, int, int>> save[N]; int c[S + 10][S + 10]; int f[N]; int32_t main() { cin.tie(0)->sync_with_stdio(0); cin >> n; for (int i = 1; i <= n; ++i) cin >> d[i] >> x[i]; f[1] = 1; for (int i = 1; i <= n; ++i) { int& ret = f[i]; for (const auto& [size, mod, value] : save[i]) add(c[size][mod], M - value); for (int j = 1; j <= S; ++j) add(ret, c[j][i % j]); if (!d[i]) continue; if (d[i] > S) { for (int j = 1; j <= x[i]; ++j) { int t = i + j * d[i]; if (t > n) break; add(f[t], ret); } continue; } add(c[d[i]][i % d[i]], ret); save[min(1ll * n, 1ll * i + d[i] * x[i]) + 1].emplace_back(d[i], i % d[i], ret); } int answer = 0; for (int i = 1; i <= n; ++i) add(answer, f[i]); cout << answer << "\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...