제출 #1346258

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

int d[N], x[N];
int dp[N];
int 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];
        d[i] = min(d[i], n);
        x[i] = min(x[i], n);
    }
    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(n, i + d[i]);
            while(lo % d[i] != i % d[i]) lo--;
            dp[i] += (1LL*qs[d[i]][lo] - qs[d[i]][hi])%mod;
        }else{
            for(int j = 1, cur = i+d[i]; j <= x[i] && cur < n; ++j, cur += d[i]) dp[i] = (dp[i] + dp[cur])%mod;
        }
        for(int j = 1; j < S_N; ++j) qs[j][i] = (1LL*dp[i] + (i+j > n ? 0 : qs[j][i+j]))%mod;
    }
    cout << dp[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...