Submission #1047452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047452		LucaIlie	Trains (BOI24_trains)	C++17	100 / 100	145 ms	6392 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5;
const int LIM = 300;
const int MOD = 1e9 + 7;
int d[MAX_N + 1], x[MAX_N + 1], dp[MAX_N + 1], sum[LIM + 1][LIM];
vector<int> events[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++ ) {
        for ( int j = 1; j <= LIM; j++ )
            dp[i] = (dp[i] + sum[j][i % j]) % MOD;

        if ( d[i] > LIM ) {
            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;
        } else if ( d[i] != 0 ) {
            sum[d[i]][i % d[i]] = (sum[d[i]][i % d[i]] + dp[i]) % MOD;
            if ( i + (long long)x[i] * d[i] <= n )
                events[i + x[i] * d[i]].push_back( i );
        }

        for ( int j: events[i] )
            sum[d[j]][j % d[j]] = (sum[d[j]][j % d[j]] - dp[j] + MOD) % 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: 16 / 16
• Subtask 4: 34 / 34
• Subtask 5: 29 / 29