제출 #993550

#제출 시각아이디문제언어결과실행 시간메모리
993550AlperenT_Trains (BOI24_trains)C++17
58 / 100
166 ms272208 KiB
#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] && j*d[i] <= n ; j++){ ans[i] = (ans[i] + ans[j])%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" ; } /* */
#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...