Submission #1029244

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029244		vjudge1	Trains (BOI24_trains)	C++17	100 / 100	92 ms	8412 KiB

Main

#include <bits/stdc++.h>
using namespace std;

void solve() {
	int n;
	cin >> n;
	vector<int> d(n), x(n);
	for (int i=0; i<n; i++) cin >> d[i] >> x[i];

	const int mod = 1e9+7, sqrtn = 227;

	vector<vector<int>> store(sqrtn);
	for (int i=1; i<sqrtn; i++) store[i].resize(i);

	vector<vector<int>> evs(n);
	for (int i=0; i<n; i++) {
		if (d[i] < sqrtn && d[i] > 0) {
			if (i + d[i] < n) evs[i + d[i]].push_back(i + 1);
			if (i + 1LL * x[i] * d[i] + 1 < n) evs[i + x[i] * d[i] + 1].emplace_back(-(i + 1));
		}
	}

	vector<int> dp(n, 0);
	dp[0] = 1;
	for (int i=0; i<n; i++) {
		for (int j : evs[i]) {
			int jj = abs(j) - 1;
			int &target = store[d[jj]][jj%d[jj]];
			if (j < 0) {
				target -= dp[jj];
				if (target < 0) target += mod;
			} else {
				target += dp[jj];
				if (target >= mod) target -= mod;
			}
		}

		for (int j=1; j<sqrtn; j++) {
			dp[i] += store[j][i%j];
			if (dp[i] >= mod) dp[i] -= mod;
		}

		if (d[i] >= sqrtn) {
			for (int j=1; j<=x[i] && i+1LL*j*d[i]<n; j++) {
				dp[i + j*d[i]] += dp[i];
				if (dp[i + j*d[i]] >= mod) dp[i + j*d[i]] -= mod;
			}
		}
	}
	
	int ans = 0;
	for (int i=0; i<n; i++) {
		ans += dp[i];
		if (ans >= mod) ans -= mod;
	}

	cout << ans << '\n';
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int tcs = 1;
	// cin >> tcs;
	while (tcs--) {
		solve();
	}
	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 34 / 34
• Subtask 5: 29 / 29