Submission #1052932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052932		vjudge1	Trains (BOI24_trains)	C++17	50 / 100	34 ms	3576 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long
int const N=1e5+5;
int const mod=1e9+7;

int dp[N],suf[N],d[N],x[N];
int n;
void solve(){
	dp[n]=1;
	suf[n]=1;
	for(int i=n-1;i>=1;i--){
		dp[i]=1;
		if(d[i]==0){
			suf[i]=1;
			continue;
		}
		for(int j=i+d[i];j<=n;j+=d[i]){
			if(d[j]==d[i]){
				dp[i]=(dp[i]+suf[j])%mod;
				break;
			}
			dp[i]=(dp[i]+dp[j])%mod;
		}
		suf[i]=(dp[i] + (mod-1))%mod;
		for(int j=i+(d[i]*(x[i]+1)); j<=n;j++){
			if(d[i]==d[j]){
				dp[i]=((dp[i]-suf[j])+mod)%mod;
				break;
			}
			dp[i]=((dp[i]-dp[j])+mod)%mod;
		}
		suf[i]=(dp[i]+suf[i])%mod;
	}
	// for (int i = 1; i <=n; ++i)
	// 	cout<<dp[i]<<' '<<suf[i]<<endl;

	// for(int i=1;i<=n;i++)
	// 	cout<<dp[i]<<endl;
	cout<<dp[1]<<endl;
}

signed main(){
	cin>>n;
	bool b=1;
	for (int i = 1; i <=n; ++i){
		cin>>d[i]>>x[i];
		if(d[i]!=1)
			b=0;
	}
	solve();
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:46:7: warning: variable 'b' set but not used [-Wunused-but-set-variable]
   46 |  bool b=1;
      |       ^

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