Submission #1165889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165889		Iskachun	Trains (BOI24_trains)	C++17	100 / 100	411 ms	317368 KiB

Main

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
# define d first
# define x second
const ll mod = 1e9 + 7, N = 2e5;
ll acc[400][400], add[N][400], n, d[N], x[N], dp[N];
void f(ll i, ll d, ll a) {
	if (i >= n) return;
	if (a < 0) a = (a + mod) % mod;
	add[i][d] = (add[i][d] + a) % mod;
}
void solve() {
    cin >> n;
    for (ll i = 0; i < n; i++) cin >> d[i] >> x[i];
    dp[0] = 1;
    for (ll i = 0; i < n; i++) {
		for (ll j = 1; j < 400; j++) {
			ll m = i % j;
			acc[j][m] = (acc[j][m] + add[i][j]) % mod;
			dp[i] = (dp[i] + acc[j][m]) % mod;
		}
		if (d[i] == 0) continue;
		if (d[i] < 400) {
			ll j = d[i];
			f(i + j, j, dp[i]);
			f(i + j * x[i] + j, j, -dp[i]);
		} else {
			for (ll j = i + d[i], xu = 1; xu <= x[i] && j < n; xu++, j += d[i]) {
		        	dp[j] = (dp[j] + dp[i]) % mod;
			}
		}
	}
    ll ans = 0;
    for (ll i = 0; i < n; i++) (ans += dp[i]) %= mod;
    cout << ans % mod;
}
int main() {
    //freopen("filename.in", "r", stdin), freopen("filename.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t = 1; //cin >> t;
    while (t--) solve();
}

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