Submission #1345496

#TimeUsernameProblemLanguageResultExecution timeMemory
1345496wangzhiyi33Trains (BOI24_trains)C++20
100 / 100
175 ms277512 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define fir first
#define sec second
#define pb push_back
#pragma GCC optimize("O3,unroll-loops")
const int mod=1e9+7,maxn=1e5,blk=350;
int sum[maxn+blk][blk+1];
int dp[maxn+2];

signed main(){
    int n; cin>>n;
    int d[n+1],x[n+1];
    for(int q=1;q<=n;q++){
        cin>>d[q]>>x[q];
    }

    int ans=0;
    for(int q=n;q>=1;q--){
        if(d[q]>=blk){
            int tot=0;
            for(int w=q+d[q];w<=min(n,q+(x[q]*d[q]));w+=d[q]){
                tot+=dp[w];tot%=mod;
            }
            dp[q]=tot;
        }
        else{
            int tot=sum[q+d[q]][d[q]];
            int lst=q+(x[q]+1)*d[q];
            if(lst<=n){
                tot-=sum[lst][d[q]];
            }
            tot%=mod; tot=(tot+mod)%mod;
            dp[q]=tot;
        }
        dp[q]++;
        for(int w=1;w<=blk;w++){
            sum[q][w]=sum[q+w][w]+dp[q];
            sum[q][w]%=mod;
        }
    }
    cout<<dp[1]<<endl;
}
#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...