Submission #1324520

#TimeUsernameProblemLanguageResultExecution timeMemory
1324520boclobanchatTrains (BOI24_trains)C++20
34 / 100
284 ms257080 KiB
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const int sqr=320;
const long long mod=1e9+7;
long long dp[MAXN],pref[MAXN][sqr+5],A[MAXN],B[MAXN];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    dp[1]=1;
    long long ans=0;
    for(int i=1;i<=n;i++)
    {
    	cin>>A[i]>>B[i];
    	for(int j=1;j<=sqr;j++)
    	{
    		if(i>=j) pref[i][j]=(pref[i][j]+pref[i-j][j])%mod;
    		dp[i]=(dp[i]+pref[i][j])%mod;
		}
		ans=(ans+dp[i])%mod;
    	if(A[i]&&A[i]<=sqr)
    	{
    		if(B[i]) pref[i+A[i]][A[i]]=(pref[i+A[i]][A[i]]+dp[i])%mod;
    		if(i+A[i]*(B[i]+1)<=n) pref[i+A[i]*(B[i]+1)][A[i]]=(pref[i+A[i]*(B[i]+1)][A[i]]-dp[i]+mod)%mod;
		}
		else if(A[i]) for(int j=i+A[i],cnt=1;j<=n&&cnt<=B[i];j+=A[i],cnt++) dp[j]=(dp[j]+dp[i])%mod;
	}
	cout<<ans;
}
#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...