Submission #1047068

#TimeUsernameProblemLanguageResultExecution timeMemory
1047068raczekTrains (BOI24_trains)C++17
21 / 100
2095 ms3928 KiB
#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG 
auto& operator <<(auto& o, pair<auto, auto> p) {return o<<"{"<<p.first<<", "<<p.second<<"}";}
auto& operator <<(auto& o, auto x) {o<<"{"; for(auto v : x) o<<v<<", "; return o<<"}";}
#define debug(X) cerr<<"["#X"]: "<<X<<endl;
#else
#define debug(X) {}
#endif
#define int long long
const int MOD = 1e9+7;
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	vector<int> dp(n);
	vector<pair<int, int> > trains(n);
	for(auto& v : trains) cin>>v.first>>v.second;
	for(int i=n-1;i>=0;i--)
	{
		int d = trains[i].first, x = trains[i].second;
		if(d == 0) continue;
		for(int k = i+d;k<=i+d*x && k < n;k+=d)
		{
			dp[i] += dp[k] + 1;
			dp[i] %= MOD;
		}
	}
	cout<<(dp[0]+1)%MOD;
}
#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...