Submission #1041397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041397		owoovo	Trains (BOI24_trains)	C++17	100 / 100	212 ms	245840 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
using namespace std;
const ll p=1e9+7;
const int maxn=300;
int n;
ll dp[100010],pp[100010][310],ans;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    dp[1]=1;
    cin>>n;
    for(int i=1;i<=n;i++){
        ll d,x;
        cin>>d>>x;//
        for(int j=1;j<=min(maxn,i);j++){
            pp[i][j]+=pp[i-j][j];
            pp[i][j]%=p;
            dp[i]+=pp[i][j];
            dp[i]%=p;
        }
        ans+=dp[i];
        ans%=p;
        if(d>maxn){
            for(ll j=i+d,t=1;j<=n&&t<=x;j+=d,t++){
                dp[j]+=dp[i];
                dp[j]%=p;
            }
        }else{
            if(d==0)continue;
            if(i+d<=n){
                pp[i+d][d]+=dp[i];
                pp[i+d][d]%=p;
            }
            if(i+d*(x+1)<=n){
                pp[i+d*(x+1)][d]-=dp[i];
                pp[i+d*(x+1)][d]=((pp[i+d*(x+1)][d]%p)+p)%p;
            }
        }
    }
    cout<<ans<<"\n";
    return 0;
}

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