제출 #1047452

#제출 시각아이디문제언어결과실행 시간메모리
1047452LucaIlieTrains (BOI24_trains)C++17
100 / 100
145 ms6392 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...