# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1033582 | vjudge1 | 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;
#define fi first
#define se second
#define el '\n'
#define pb push_back
#define mp make_pair
#define niggers \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL);
#define file(name) \
freopen(name ".inp", "r", stdin); \
freopen(name ".out", "w", stdout);
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int, int> pii;
typedef vector<long long> vll;
typedef vector<int> vi;
const ll MOD = 1e9 + 7;
const int inf = 1e9;
const int N = 1e2 + 5;
const int mxM = 1e3 + 5;
const int N = 2e5 + 5;
int hx[] = {-1, 0, 1, 0};
int hy[] = {0, 1, 0, -1};
ll dp[ N], d[ N], x[ N], n;
int main()
{
// freopen("b.inp", "r", stdin);
// freopen("b.out", "w", stdout);
ll pinkkiu = 1;
// cin >> pinkkiu;
while (pinkkiu--)
{
ll n; cin >> n; dp[1] = 1;
for (ll i = 1; i <= n; i++)
{
cin >> d[i] >> x[i];
if (d[i] && x[i] <= 320)
{
for (ll j = i+d[i]; j <= min(n, i+x[i]*d[i]); j += d[i])
{dp[j] += dp[i]; dp[j] %= MOD;}
}
}
vector<pair<ll,pair<ll,ll>>> v;
for (ll i = 1; i <= n; i++)
{
for (pair<ll,pair<ll,ll>> j : v) if ((i-j.fi)%j.se.fi == 0 && (i-j.fi)/j.se.fi <= j.se.se)
{dp[i] += dp[j.fi]; dp[i] %= MOD;}
if (d[i] && x[i] > 320) v.pb({i,{d[i],x[i]}});
}
ll ans = 0;
for (ll i = 1; i <= n; i++) {ans += dp[i]; ans %= MOD;}
cout << ans;
}
}