Submission #996787

#TimeUsernameProblemLanguageResultExecution timeMemory
996787siewjhTrains (BOI24_trains)C++17
100 / 100
164 ms131584 KiB
#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 = 330;
	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];
}
#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...