Submission #1047443

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047443		LucaIlie	Trains (BOI24_trains)	C++17	21 / 100	2096 ms	2644 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5;
const int MOD = 1e9 + 7;
int d[MAX_N + 1], x[MAX_N + 1], dp[MAX_N + 1];

int main() {
    int n;

    cin >> n;
    for ( int i = 1; i <= n; i++ )
        cin >> d[i] >> x[i];

    dp[1] = 1;
    for ( int i = 1; i <= n; i++ ) {
        if ( d[i] == 0 )
            continue;

        for ( int j = i + d[i]; j <= n && j <= i + (long long)x[i] * d[i]; j += d[i] )
            dp[j] = (dp[j] + dp[i]) % MOD;
    }

    int ans = 0;
    for ( int i = 1; i <= n; i++ )
        ans = (ans + dp[i]) % MOD;

    cout << ans;

    return 0;
}

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