Submission #1033584

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033584		BuzzyBeez	Trains (BOI24_trains)	C++17	100 / 100	197 ms	5644 KiB

Main

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("arch=skylake")
#include <bits/stdc++.h>
using namespace std;

const int S = 360;
const int mod = 1e9 + 7;

int dp[100008];
int bonus[S + 8][S + 8];
vector<int> upd[100008];
int d[100008], x[100008];

signed main() {
	// freopen("data.inp", "r", stdin);
	// freopen("data.ans", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, ans = 0; cin >> n; dp[1] = 1;
	for (int i = 1; i <= n; ++i) {
		cin >> d[i] >> x[i];
		if (!d[i]) x[i] = 0;
		else x[i] = min(x[i], (n - i) / d[i]);
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= S; ++j) (dp[i] += bonus[j][i % j]) %= mod;
		if (x[i] <= S) {for (int j = 1; j <= x[i]; ++j) (dp[i + j * d[i]] += dp[i]) %= mod;}
		else {
			(bonus[d[i]][i % d[i]] += dp[i]) %= mod;
			if (d[i] && x[i]) upd[i + x[i] * d[i]].push_back(i);
		}
		for (int j : upd[i]) (bonus[d[j]][j % d[j]] += (mod - dp[j])) %= mod;
		ans = (ans + dp[i]) % mod;
		// cout << d[i] << ' ' << x[i] << ' ' << dp[i] << '\n';
	}
	cout << ans;
}

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