Submission #996788

#	Time	Username	Problem	Language	Result	Execution time	Memory
996788		siewjh	Trains (BOI24_trains)	C++17	100 / 100	142 ms	119848 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int MAXN = 100355;
int suff[350][MAXN], ans[MAXN];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int nums; cin >> nums;
	vector<int> step(nums + 1), stop(nums + 1);
	for (int i = 1; i <= nums; i++){
		int amt; cin >> step[i] >> amt;
		if (step[i] != 0){
			amt = min(amt, (nums - i) / step[i]);
			stop[i] = i + amt * step[i];
		}
	}
	int bsz = 300;
	for (int i = nums; i >= 1; i--){
		ans[i] = 1;
		int ssz = step[i];
		if (ssz > bsz){
			for (int x = stop[i]; x > i; x -= ssz) ans[i] = (ans[i] + ans[x]) % mod;
		}
		else if (ssz != 0){
			ans[i] = (ans[i] + suff[ssz][i + ssz] - suff[ssz][stop[i] + ssz] + mod) % mod;
		}
		for (int x = 1; x <= bsz; x++) suff[x][i] = (suff[x][i + x] + ans[i]) % mod;
	}
	cout << ans[1];
}

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