Submission #994579

#TimeUsernameProblemLanguageResultExecution timeMemory
994579kymTrains (BOI24_trains)C++14
50 / 100
176 ms10976 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #ifdef LOCAL void debug_out() {cerr<<endl;} template <typename Head, typename... Tail> void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);} #define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__) #else #define debug(...) #endif const int MAXN = 100005; const int inf=1000000500ll; const long long oo =1000000000000000500ll; const int MOD = (int)1e9+7; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); typedef pair<int,int> pi; const int sqn=400; int n; int D[MAXN], X[MAXN]; int dp[MAXN]; int R[sqn+5][sqn+5]; vector<array<int,3>> C[MAXN]; // at C_i, we need to remove x.first from x.second int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; dp[1]=1; for(int i=1;i<=n;i++){ cin>>D[i]>>X[i]; } int ans=0; for(int i=1;i<=n;i++){ for(int r=1;r<=sqn;r++){ dp[i]=(dp[i] + R[r][i%r])%MOD; } if(D[i] > sqn){ for(int t=1;t<=X[i];t++){ int idx=i+t*D[i]; if(idx<=n){ dp[idx] = (dp[idx] + dp[i])%MOD; } else{ break; } } } else{ R[D[i]][i%D[i]]=(R[D[i]][i%D[i]]+dp[i])%MOD; int idx=min(n+1,i+X[i]*D[i]); C[idx].push_back({D[i],i%D[i],dp[i]}); } for(auto x:C[i]){ R[x[0]][x[1]]=(R[x[0]][x[1]]-x[2]+MOD)%MOD; } ans=(ans+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...