Submission #994563

#	Time	Username	Problem	Language	Result	Execution time	Memory
994563		pavement	Trains (BOI24_trains)	C++17	21 / 100	2096 ms	86992 KiB

Main

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

#define pb push_back

const int MOD = (int)1e9 + 7, LIM = 200, LIM2 = 200;
int N, d[100005], x[100005], dp[100005];
vector<int> vec[LIM2 + 5][LIM2];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> d[i] >> x[i];
	}
	for (int i = N; i >= 1; i--) {
		if (d[i]) {
			int num_stops = min(x[i], (N - i) / d[i]);
			if (num_stops <= LIM) {
				for (int j = 1; j <= num_stops; j++) {
					dp[i] = (dp[i] + dp[i + j * d[i]]) % MOD;
				}
			} else {
				assert(d[i] <= LIM2);
				for (int j = 1; j <= num_stops; j++) {
					dp[i] = (dp[i] + vec[d[i]][i % d[i]][vec[d[i]][i % d[i]].size() - j]) % MOD;
				}
			}
		}
		dp[i] = (dp[i] + 1) % MOD;
		for (int j = 1; j <= LIM2; j++) {
			vec[j][i % j].pb(dp[i]);
		}
	}
	cout << dp[1] << '\n';
}

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