Submission #1052923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052923		vjudge1	Trains (BOI24_trains)	C++17	100 / 100	74 ms	7196 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll N = 1e5 + 10, mod = 1e9 + 7, D = 100;
ll n, dp[N], sm[D][D], a[N][2];
vector<ll> del[N];

void add(ll &x, ll y){
    x += y;
    if (x < 0) x += mod;
    if (x >= mod) x -= mod;
}

int main(){
    cin >> n;
    for (ll i = 1; i <= n; i ++)
        cin >> a[i][0] >> a[i][1];

    dp[1] = 1;
    for (ll i = 1; i <= n; i ++){
        for (ll d = 1; d < D; d ++)
            add(dp[i], sm[d][i % d]);

        for (ll l : del[i]){
            // cout << "At " << i << " deleting " << l << " which is " << -dp[l] << " and contents " << a[l][0] << ", " << l % a[l][0] << endl;
            add(sm[a[l][0]][l % a[l][0]], -dp[l]);
        }

        if (!a[i][0] or !a[i][1]) continue;

        if (a[i][0] >= D){
            for (ll j = i + a[i][0]; j <= n and a[i][1]; j += a[i][0], a[i][1]--)
                add(dp[j], dp[i]);
        }
        else{
            add(sm[a[i][0]][i % a[i][0]], dp[i]);
            ll r = 1ll * i + 1ll * a[i][0] * a[i][1];
            // cout << "Adding " << dp[i] << " on " << a[i][0] << ", " << i % a[i][0] << endl;
            if (r <= n)
                del[r].push_back(i);
        }
    }

    ll ans = 0;
    for (ll i = 1; i <= n; i ++){
        // cout << i << " : " << dp[i] << endl;
        add(ans, dp[i]);
    }

    ans %= mod;
    ans += mod;
    ans %= mod;

    cout << ans << endl;
}

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