Submission #999492

#	Time	Username	Problem	Language	Result	Execution time	Memory
999492		esomer	Trains (BOI24_trains)	C++17	100 / 100	618 ms	358024 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7;

typedef long long ll;

ll sumLast(vector<ll>& suf, int x){
	if(x >= (int)suf.size()) return suf.back();
	if(!x) return 0;
	return (suf.back() + MOD - suf[(int)suf.size() - x - 1]) % MOD;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;
	vector<int> x(N), d(N);
	for(int i = 0; i < N; i++){
		cin >> d[i] >> x[i];
	}
	int sqr = sqrt(N);
	vector<vector<vector<ll>>> suffix(sqr);
	//It's efficiente because each index will be in sqrt vectors.
	for(int i = 1; i < sqr; i++){
		suffix[i].assign(i, {0});
	}
	vector<ll> dp(N, 0);
	for(int i = N - 1; i >= 0; i--){
		dp[i]++; //Just ending there.
		if(d[i] >= sqr){
			int curr = i + d[i];
			int currMult = 1;
			while(curr < N && currMult <= x[i]){
				dp[i] += dp[curr]; dp[i] %= MOD;
				currMult++;
				curr += d[i];
			}
		}else if(d[i] > 0){
			int md = i % d[i];
			//I want the sum of the last x ones.
			dp[i] += sumLast(suffix[d[i]][md], x[i]);
			dp[i] %= MOD;
		}
		for(int div = 1; div < sqr; div++){
			int md = i % div;
			suffix[div][md].push_back((suffix[div][md].back() + dp[i]) % MOD);
		}
	}
	cout << dp[0] << "\n";
}

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