Submission #1214820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214820		biank	Trains (BOI24_trains)	C++20	100 / 100	101 ms	6212 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i,n) for(int i=0;i<int(n);i++)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define dforn(i,n) for(int i=int(n)-1;i>=0;i--)
#define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--)
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
 
typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef pair<int,int> ii;
 
const int MOD=1e9+7;
 
void add(int &x, int v){
    if((x+=v)>=MOD) x-=MOD;
}
 
void sub(int &x, int v){
    if((x-=v)<0) x+=MOD;
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin>>n;
    vi d(n),x(n);
    forn(i,n){
        cin>>d[i]>>x[i];
    }
    const int S=320;
    vi dp(n,0);
    dp[0]=1;
    vector<vi> dp2(S,vi(S));
    vector<vi> erase(n);
    forn(i,n){
        forsn(j,1,S) add(dp[i],dp2[j][i%j]);
        if(d[i]!=0&&d[i]<S){
            add(dp2[d[i]][i%d[i]],dp[i]);
            ll last=i+1LL*x[i]*d[i];
            if(last<n){
                erase[last].pb(i);
            }
        }else if(d[i]!=0){
            forsn(t,1,x[i]+1){
                if(i+1LL*t*d[i]>=n) break;
                int j=i+t*d[i];
                add(dp[j],dp[i]);
            }
        }
        for(int j:erase[i]){
            sub(dp2[d[j]][j%d[j]],dp[j]);
        }
    }
    int ans=0;
    forn(i,n){
        add(ans,dp[i]);
    }
    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