제출 #1345205

#제출 시각아이디문제언어결과실행 시간메모리
1345205ZicrusTrains (BOI24_trains)C++20
34 / 100
303 ms239064 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) x.begin(), x.end()
#define sz(x) (ll)(x).size()
constexpr ll inf = 4e18;
mt19937 mt(time(0));

const ll mod = 1000000007;
const ll SQRT = 300;

void solve() {
    ll n; cin >> n;
    vector<pll> trains(n);
    for (ll i = 0; i < n; i++) {
        auto &[d, k] = trains[i];
        cin >> d >> k;
        ll s = i % k;
        if (d > 0) {
            ll mxk = (n - s - 1) / d;
            k = min(k, mxk);
        }
        assert(i + k * d < n);
    }

    vector<ll> dp(n, 1);
    vector<vector<ll>> sdp(SQRT, vector<ll>(n + SQRT));
    for (ll i = n; i--;) {
        auto &[d, k] = trains[i];
        if (d < SQRT) {
            dp[i] = ((sdp[d][i + d] - sdp[d][i + d + k * d] + 1) % mod + mod) % mod;
        }
        else {
            for (ll j = 1; j <= k; j++) {
                (dp[i] += dp[i + j * d]) %= mod;
            }
        }

        for (ll j = 1; j < SQRT; j++) {
            sdp[j][i] = (sdp[j][i + j] + dp[i]) % mod;
        }
    }
    cout << dp[0] << '\n';
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    solve();
}
#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...