Submission #1180201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180201		peteza	Trains (BOI24_trains)	C++20	100 / 100	295 ms	319824 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9+7;

int n;
ll dd[100405], dura[100405];
ll dp[100405];
ll qs[100405][405];
int sq = 400;

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n;
    for(int i=1;i<=n;i++) {
        cin >> dd[i] >> dura[i];
    }
    for(int i=n;i>=1;i--) {
        dp[i] = 1;
        if(dd[i]) {
            if(dd[i] >= sq) {
                //calculate directly
                for(int j=1, ci=i + dd[i];j<=dura[i] && ci <= n;j++, ci += dd[i]) {
                    dp[i] += dp[ci];
                    if(dp[i] >= mod) dp[i] -= mod;
                }
            } else {
                dp[i] = dp[i] + (i+dd[i] > n ? 0 : qs[i+dd[i]][dd[i]]) - (i+dd[i]*(dura[i]+1) > n ? 0 : qs[i+dd[i]*(dura[i]+1)][dd[i]]);
                while(dp[i] < 0) dp[i] += mod;
                while(dp[i] >= mod) dp[i] -= mod;
            }
        }
        for(int cd=1;cd<=sq;cd++) {
            qs[i][cd] = qs[i+cd][cd] + dp[i];
            if(qs[i][cd] >= mod) qs[i][cd] -= mod;
        }
        //cout << dp
    }
    cout << dp[1];
}

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