Submission #1052924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052924		vjudge1	Trains (BOI24_trains)	C++17	100 / 100	71 ms	7260 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])
            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];
            if (r <= n)
                del[r].push_back(i);
        }
    }

    ll ans = 0;
    for (ll i = 1; i <= n; i ++)
        add(ans, dp[i]);

    cout << ans << endl;
}

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