Submission #1047068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047068		raczek	Trains (BOI24_trains)	C++17	21 / 100	2095 ms	3928 KiB

Main

#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;
}

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