제출 #1179304

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1179304		gyg	Trains (BOI24_trains)	C++20	100 / 100	192 ms	11304 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define arr array 
#define vec vector 
const int N = 1e5 + 5, K = 325, MD = 1e9 + 7;

int n;
arr<int, N> d, s;

int md(int x) { return (x + MD) % MD; }
arr<int, N> dp;

arr<arr<int, K>, K> add;
arr<vec<vec<int>>, N> rmv;

void cmp() {
    for (int i = 1; i <= n; i++) {
        if (i == 1) dp[i] = 1;
        else {
            for (int j = 1; j <= 320; j++) {
                dp[i] = md(dp[i] + add[j][i % j]);
            }
        }

        for (vec<int> x : rmv[i]) {
            add[x[0]][x[1]] = md(add[x[0]][x[1]] - x[2]);
        }
        if (!d[i] || !s[i]) continue;

        if (d[i] <= 320) {
            add[d[i]][i % d[i]] = md(add[d[i]][i % d[i]] + dp[i]);
            if (i + s[i] * d[i] <= n) {
                // cout << i + s[i] * d[i] << " " << d[i] << " " << i % d[i] << '\n';
                rmv[i + s[i] * d[i]].push_back({d[i], i % d[i], dp[i]});
            }
        } else {
            for (int j = i + d[i]; j <= min(i + s[i] * d[i], n); j += d[i]) {
                dp[j] = md(dp[j] + dp[i]);
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) ans = md(ans + dp[i]);
    cout << ans << '\n';
}

signed main() {
    // freopen("in", "r", stdin);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> d[i] >> s[i];

    cmp();
}

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