Submission #1049359

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049359		aymanrs	Trains (BOI24_trains)	C++17	100 / 100	125 ms	128336 KiB

Main

#include<bits/stdc++.h>
const int M = 1e9+7;
using namespace std;
int fx(int x){
    if(x<0) return x+M;
    if(x>=M) return x-M;
    return x;
}
void solve(){
    int n;cin >> n;
    long long d[n],x[n];
    for(int i = 0;i < n;i++) cin >> d[i] >> x[i];
    int s = sqrt(n);
    int su[s+1][n];
    int dp[n];
    for(int i = n-1;i >= 0;i--){
        dp[i]=1;
        if(!d[i] || !x[i] || i+d[i] >= n) goto upd;
        if(d[i]<=s) dp[i] = fx(1+su[d[i]][i+d[i]]-(i+(x[i]+1)*d[i]<n ? su[d[i]][i+(x[i]+1)*d[i]] : 0));
        else {
            for(int j = 1;j <= x[i] && i+j*d[i] < n;j++) dp[i] = fx(dp[i]+dp[i+j*d[i]]);
        }
        upd:
        for(int j = 1;j <= s;j++) su[j][i] = fx(dp[i]+(i+j < n ? su[j][i+j] : 0));
    }
    cout << dp[0] << '\n';

}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
}

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