Submission #1267314

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267314		g4yuhg	Trains (BOI24_trains)	C++20	100 / 100	667 ms	359480 KiB

Main

//Huyduocdithitp
#include <bits/stdc++.h>
typedef long long ll;
#define pii pair<ll, ll> 
#define MP make_pair
#define fi first
#define se second
#define TASK "connect"
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);
#define N 100005
#define LOG 18
#define endl '\n'
using namespace std;

const ll mod = 1e9 + 7;
const ll S = 320;

void add(ll &u, ll v) {
	u += v;
	if (u >= mod) u -= mod;
}

ll n;
ll d[N], x[N], dp[N];

vector<ll> pf[S + 2][S + 2];

void solve() {
	for (int i = n; i >= 1; i --) {
		dp[i] = 1;
		if (d[i] == 0) {
			dp[i] = 1;
		}
		else {
			if (x[i] <= S || d[i] > S) {
				for (int t = 1; t <= x[i]; t ++) {
					if (i + t * d[i] > n) break;
					add(dp[i], dp[i + t * d[i]]);
				}
			}
			else {
				ll du = i % d[i];
				ll val = 0;
				if (pf[d[i]][du].size() > 0) {
					ll sz = pf[d[i]][du].size(); 
					val = pf[d[i]][du][sz - 1];
					if (sz - x[i] - 1 >= 0) {
						val = val - pf[d[i]][du][sz - x[i] - 1];
						val = (val % mod + mod) % mod;
					}
				}
				add(dp[i], val);
			}
		}
		/*if (i == 1) {
			for (auto it : pf[1][0]) {
				cout << it << " ";
			}
			cout << endl;
		}*/
		for (int j = 1; j <= S; j ++) {
			ll du = i % j;
			if (pf[j][du].size() > 0) {
				pf[j][du].push_back( (pf[j][du].back() + dp[i]) % mod );
			}
			else {
				pf[j][du].push_back(dp[i]);
			}
		}
		//cout << i << " " << dp[i] << endl;
	}
	cout << dp[1];
}

signed main(void) {
	faster;
	
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> d[i] >> x[i];
	}
	
	solve();
	
	return 0;
}

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