제출 #1346268

#제출 시각아이디문제언어결과실행 시간메모리
1346268Zone_zoneeTrains (BOI24_trains)C++20
100 / 100
189 ms251888 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5+10, S_N = 317, mod = 1e9+7;

ll d[N], x[N];
ll dp[N];
ll qs[S_N][2*N];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> d[i] >> x[i];
    }
    for(int i = n; i >= 1; --i){
        dp[i] = 1;
        if(d[i] != 0) if(d[i] < S_N){
            int hi = min(1LL*n+d[i], i + 1LL*(x[i]+1)*d[i]);
            while(hi % d[i] != i % d[i]) hi--;
            int lo = min(1LL*n, i + d[i]);
            while(lo % d[i] != i % d[i]) lo--;
            dp[i] += (1LL*qs[d[i]][lo] - qs[d[i]][hi] + mod)%mod;
        }else{
            for(int j = 1, cur = i+d[i]; j <= x[i] && cur <= n; ++j, cur += d[i]) dp[i] = (1LL*dp[i] + dp[cur])%mod;
        }
        for(int j = 1; j < S_N; ++j) qs[j][i] = (1LL*dp[i] + qs[j][i+j])%mod;
    }
    cout << dp[1]%mod << '\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...