Submission #1180201

#TimeUsernameProblemLanguageResultExecution timeMemory
1180201petezaTrains (BOI24_trains)C++20
100 / 100
295 ms319824 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9+7;

int n;
ll dd[100405], dura[100405];
ll dp[100405];
ll qs[100405][405];
int sq = 400;

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n;
    for(int i=1;i<=n;i++) {
        cin >> dd[i] >> dura[i];
    }
    for(int i=n;i>=1;i--) {
        dp[i] = 1;
        if(dd[i]) {
            if(dd[i] >= sq) {
                //calculate directly
                for(int j=1, ci=i + dd[i];j<=dura[i] && ci <= n;j++, ci += dd[i]) {
                    dp[i] += dp[ci];
                    if(dp[i] >= mod) dp[i] -= mod;
                }
            } else {
                dp[i] = dp[i] + (i+dd[i] > n ? 0 : qs[i+dd[i]][dd[i]]) - (i+dd[i]*(dura[i]+1) > n ? 0 : qs[i+dd[i]*(dura[i]+1)][dd[i]]);
                while(dp[i] < 0) dp[i] += mod;
                while(dp[i] >= mod) dp[i] -= mod;
            }
        }
        for(int cd=1;cd<=sq;cd++) {
            qs[i][cd] = qs[i+cd][cd] + dp[i];
            if(qs[i][cd] >= mod) qs[i][cd] -= mod;
        }
        //cout << dp
    }
    cout << dp[1];
}
#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...