Submission #1064591

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064591		Boomyday	Trains (BOI24_trains)	C++17	100 / 100	683 ms	364568 KiB

Main

//
// Created by adavy on 8/18/2024.
//
#include <bits/stdc++.h>


using namespace std;

using ll = long long;
const ll MOD = 1e9 + 7;

int main(){
     ll N; cin >> N;
     vector<ll> d(N),x(N);
     for(int i=0;i<N;++i){
         cin >> d[i] >> x[i];
     }
     vector<ll> dp(N,1);
     ll B = floor(sqrt(N))+1;
     vector<vector<vector<ll>>> prefs(B); // type, modulo, preflist
     for(int i=0;i<B;++i){
         prefs[i] = vector<vector<ll>>(B,{0});
     }



     for(int i=N-1;i>=0;--i){
         if (d[i] == 0) {}
         else if (d[i] >= B){

             for(int j=i+d[i]; j<=min(N-1, i+x[i]*d[i]);j+=d[i]){
                 dp[i] += dp[j];
                 dp[i] %= MOD;
             }
         }
         else {
             ll psz = prefs[d[i]][i%d[i]].size();

             dp[i] += prefs[d[i]][i%d[i]][psz-1] - prefs[d[i]][i%d[i]][max(0LL,psz-x[i]-1)] + MOD;
             dp[i] %= MOD;

         }
         for(int j=1;j<B;++j){
             prefs[j][i%j].push_back((prefs[j][i%j].back()+dp[i])%MOD);
         }
     }
     cout << dp[0] << endl;



    return 0;
}

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