# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1250724 | mingga | Trains (BOI24_trains) | C++20 | 236 ms | 8480 KiB |
// Author: caption_mingle
#include "bits/stdc++.h"
using namespace std;
#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define int long long
const int mod = 1e9 + 7;
const int inf = 2e9;
const int N = 1e5 + 7;
const int B = 330;
int n, a[N], x[N], d[B][B], dp[N];
vector<pair<int, int>> ev[N];
int add(int x, int y) {
x += y;
if(x >= mod) x -= mod;
if(x < 0) x += mod;
return x;
}
int mul(int x, int y) {
return (1ll * x * y) % mod;
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
#define task ""
if(fopen(task ".INP", "r")) {
freopen(task ".INP", "r", stdin);
freopen(task ".OUT", "w", stdout);
}
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i] >> x[i];
}
dp[1] = 1;
for(int i = 1; i <= n; i++) {
for(int j = 1; j < B; j++) {
dp[i] = add(dp[i], d[j][i % j]);
}
int cur_gap = a[i], num_stat = x[i];
if(cur_gap > 0) {
int fir_stat = i + cur_gap;
int lst_stat = i + cur_gap * min(num_stat, (n - i) / cur_gap);
if(cur_gap >= B) {
for(int j = fir_stat; j <= lst_stat; j += cur_gap) {
dp[j] = add(dp[j], dp[i]);
}
} else {
d[cur_gap][i % cur_gap] = add(d[cur_gap][i % cur_gap], dp[i]);
ev[lst_stat].pb({i, cur_gap});
}
}
for(auto [pre, gap] : ev[i]) {
d[gap][pre % gap] = add(d[gap][pre % gap], -dp[pre]);
}
}
int ans = 0;
for(int i = 1; i <= n; i++) {
ans = add(ans, dp[i]);
}
cout << ans << ln;
cerr << "\nTime: " << clock() * 1000 / CLOCKS_PER_SEC;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |