Submission #1000121

#TimeUsernameProblemLanguageResultExecution timeMemory
1000121OAleksaTrains (BOI24_trains)C++14
21 / 100
2050 ms4724 KiB
#include <bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;
const int N = 2e5 + 69;
const int mod = 1e9 + 7;
int n, d[N], x[N], dp[N];
int add(int x, int y) {
	x += y;
	if (x >= mod)
		x -= mod;
	return x;
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int tt = 1;
	//cin >> tt;
	while (tt--) {
		cin >> n;
		for (int i = 1;i <= n;i++)
			cin >> d[i] >> x[i];
		dp[1] = 1;
		for (int i = 1;i <= n;i++) {
			if (d[i] == 0)
				continue;
			for (int j = i + d[i], j1 = 1;j <= n && j1 <= x[i];j += d[i], j1++) 
				dp[j] = add(dp[j], dp[i]);
		}
		int ans = 0;
		for (int i = 1;i <= n;i++)
			ans = add(ans, dp[i]);
		cout << ans;
	}
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...