Submission #1049411

#TimeUsernameProblemLanguageResultExecution timeMemory
1049411YassirSalamaTrains (BOI24_trains)C++17
100 / 100
186 ms256848 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define pb push_back #ifdef IOI template<typename T> void dbg(const T&t){ cout<<t<<endl; } template<typename T,typename... Args> void dbg(const T& t,const Args&... args){ cout<<t<<" , "; dbg(args...); } #define dbg(...) cout<<"("<<#__VA_ARGS__<<"): ";dbg(__VA_ARGS__); #else #define dbg(...) 1337; #endif #define F first #define S second const int maxn=1e5+100; const int mod=1e9+7; signed main(){ int n; cin>>n; vector<pair<int,int>> v(n); for(int i=0;i<n;i++){ cin>>v[i].F>>v[i].S; } int dp[n]; int t=sqrt(n)+1; vector<vector<int>> cnt(n,vector<int>(t+2,0)); memset(dp,0,sizeof(dp)); for(int i=n-1;i>=0;i--){ dp[i]=1; int a=v[i].F; int b=v[i].S; if(a==0||b==0) { for(int j=1;j<=t;j++) { cnt[i][j]=dp[i]; if(i+j<n) cnt[i][j]+=cnt[i+j][j]; cnt[i][j]%=mod; } continue; } if(a<=t){ if(i+a<n) dp[i]+=cnt[i+a][a]%mod; dp[i]%=mod; if(i+b*a+a<n) dp[i]-=cnt[i+b*a+a][a]; dp[i]%=mod; if(dp[i]<0) dp[i]+=mod; }else{ int j=i; while(b){ b--; j+=a; if(j>=n) break; dp[i]+=dp[j]; dp[i]%=mod; } } for(int j=1;j<=t;j++) { cnt[i][j]=dp[i]; if(i+j<n) cnt[i][j]+=cnt[i+j][j]; cnt[i][j]%=mod; } } dp[0]%=mod; if(dp[0]<0) dp[0]+=mod; cout<<dp[0]<<endl; }
#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...