Submission #993551

#	Time	Username	Problem	Language	Result	Execution time	Memory
993551		AlperenT_	Trains (BOI24_trains)	C++17	100 / 100	173 ms	274000 KiB

Main

#include <bits/stdc++.h>
 
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double
#define int long long 
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i, a , b) for(int i=a;i >= b;i--)
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 2e5+10  ,  N = 1e5 +1 , lg = 20 , maxq = 202 , sq = 333   , inf = 1e18  , maxk = 2022  , mod =1e9 + 7;
int s[maxn][sq+2] , d[maxn] , x[maxn] , ans[maxn] ; 
vector <int> vec[maxn] ; 

signed main(){
  ios_base::sync_with_stdio(false); cin.tie(0);   
  int n ;
  cin >> n ;
  rep(i , 1, n){
    cin >> d[i] >> x[i] ;
    if(d[i] <= sq && i+d[i]*(x[i] + 1) <= n){
      vec[i+d[i]*(x[i]+1)].pb(i); 
    }
  }
  per(i , n , 1){
    if(d[i] <= sq){
      ans[i] = (ans[i] + 1 + s[i+d[i]][d[i]] )%mod ; 
    }else{
      ans[i] =1 ;
      for(int j = 1 ; j <= x[i] && i+j*d[i] <= n ; j++){
        ans[i] = (ans[i] + ans[i+j*d[i]])%mod ;
      }
    }
    rep(j ,1  , sq){
      s[i][j] = (ans[i]+ s[i+j][j])%mod ;
    }
    for(int x : vec[i]){
      ans[x] = (ans[x] - s[i][d[x]] + mod)%mod ;
    }
  }
  cout << ans[1] << "\n" ;
}

/*

*/

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