# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1125956 | quanquai | Trains (BOI24_trains) | C++20 | 329 ms | 164560 KiB |
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n; cin >> n;
vector<pair<int, int>> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i].first >> a[i].second;
}
int block_size = 200;
const int mod = (int) 1e9 + 7;
vector<int64_t> dp(n + 1, 0);
vector<vector<int64_t>> diff(block_size + 5, vector<int64_t> (n + 1, 0));
dp[1] = 1;
int64_t ans = 0;
for (int i = 1; i <= n; i++) {
int d = a[i].first, step = a[i].second;
int64_t ways = dp[i];
for (int j = 1; j <= block_size; j++) {
if (i - j >= 0) diff[j][i] += diff[j][i - j];
diff[j][i] %= mod;
ways += diff[j][i];
ways %= mod;
}
ans += ways;
ans %= mod;
# | 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... |