Submission #1276709

#TimeUsernameProblemLanguageResultExecution timeMemory
1276709HiepVu217Trains (BOI24_trains)C++20
100 / 100
253 ms125708 KiB
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 17, B = 317, M = 1e9 + 7; int n, d[N], x[N], f[N], s[N][B]; void add (int &a, long long b) { a += b; if (a >= M) { a -= M; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for (int i = 1; i <= n; ++i) { cin >> d[i] >> x[i]; } for (int i = n; i; --i) { int c = d[i]; f[i] = 1; if (c) { int k = min (x[i], (n - i) / d[i]); if (k <= B) { for (int j = i + c; j <= i + k * c; j += c) { add (f[i], f[j]); } } else { add (f[i], s[i + c][c] - s[i + (k + 1) * c][c] + M); } } for (int j = 1; j < B; ++j) { s[i][j] = (s[i + j][j] + f[i]) % M; } } cout << f[1]; }
#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...