| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1033582 | vjudge1 | Trains (BOI24_trains) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
}