# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1097202 | manhlinh1501 | Trains (BOI24_trains) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int MAXN = 1e5 + 5;
using pii = pair<int, int>;
const i64 MOD = 1e9 + 7;
const int BLOCK = 400;
int N;
pii a[MAXN];
int dp[MAXN];
int b[BLOCK][MAXN];
void add(int &a, int b) {
a += b;
if(a >= MOD) a -= MOD;
if(a < 0) a += MOD;
}
void update(i64 p, int x, int res) {
if(p > N) return;
add(b[x][p], res);
}
signed main() {
#define TASK ""
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N;
for(int i = 1; i <= N; i++) cin >> a[i].first >> a[i].second;
dp[1] = 1;
for(int i = 1; i <= N; i++) {
for(int j = 1; j < BLOCK; j++) {
if(i >= j)
add(b[j][i], b[j][i - j]);
}
for(int j = 1; j < BLOCK; j++)
add(dp[i], b[j][i]);
if(a[i].first == 0) continue;
if(a[i].first < BLOCK) {
update(1LL * i + a[i].first, a[i].first, dp[i]);
update(1LL * i + 1LL * a[i].first * a[i].second + a[i].first, a[i].first, -dp[i]);
} else {
for(int j = 1; j <= a[i].second and i + j * a[i].first <= N; j++)
add(dp[i + j * a[i].first], dp[i]);
}
}
i64 ans = 0;
for(int i = 1; i <= N; i++) add(ans, dp[i]);
cout << ans;
}