Submission #1203243

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203243		AlgorithmWarrior	Trains (BOI24_trains)	C++20	100 / 100	229 ms	127232 KiB

Main

#include <bits/stdc++.h>

using namespace std;

void maxself(int& a,int b){
    if(a<b)
        a=b;
}

int const MAX=1e5+5;
int const MOD=1e9+7;
int const BLOCK_SIZE=316;
int dp[MAX];
int lg[MAX],rep[MAX];
int sum[MAX][BLOCK_SIZE+5];
int n;

void read(){
    cin>>n;
    int i;
    for(i=1;i<=n;++i){
        cin>>lg[i]>>rep[i];
    }
}

int calc_dp(){
    dp[1]=1;
    int i,j;
    int ans=0;
    for(i=1;i<=n;++i){
        for(j=1;j<=BLOCK_SIZE;++j){
            if(i-j>0){
                sum[i][j]+=sum[i-j][j];
                sum[i][j]%=MOD;
            }
            dp[i]+=sum[i][j];
            dp[i]%=MOD;
        }
        if(lg[i] && rep[i]){
            if(lg[i]<=BLOCK_SIZE){
                if(i+lg[i]<=n){
                    sum[i+lg[i]][lg[i]]+=dp[i];
                    sum[i+lg[i]][lg[i]]%=MOD;
                }
                if(i+1LL*lg[i]*(rep[i]+1)<=n){
                    sum[i+lg[i]*(rep[i]+1)][lg[i]]+=MOD-dp[i];
                    sum[i+lg[i]*(rep[i]+1)][lg[i]]%=MOD;
                }
            }
            else{
                for(j=i+lg[i];j<=i+1LL*lg[i]*rep[i] && j<=n;j+=lg[i]){
                    dp[j]+=dp[i];
                    dp[j]%=MOD;
                }
            }
        }
        ans+=dp[i];
        ans%=MOD;
    }
    return ans;
}

void write(int ans){
    cout<<ans;
}

int main()
{
    read();
    write(calc_dp());
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 34 / 34
• Subtask 5: 29 / 29