제출 #1149135

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1149135		bobo	Trains (BOI24_trains)	C++20	100 / 100	1959 ms	266240 KiB

Main

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

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

#define int long long
#define all(x) x.begin(), x.end()

const int mod = 1000000007;
const int S = 330;
const int N = 1e5 + 5;

int n, d[N], x[N], dp[N], de[N], ans = 0;
vector<int> rm[N];
int lz[N][S];

int32_t main() {
    ios::sync_with_stdio(0); 
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> d[i] >> x[i];
        if (d[i] == 0 || d[i] > n) continue;
        int dest = i;
        for (int j = i; j <= min(n, i + x[i] * d[i]); j += d[i]) dest = j;
        rm[dest].push_back(i);
        de[i] = dest;
    }
    dp[1] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < S; j++) dp[i] = (dp[i] + lz[i][j]) % mod;
        for (int train : rm[i]) if (d[train] < S) lz[i][d[train]] = (lz[i][d[train]] - dp[train] + mod) % mod;
        if (d[i] >= S) {
            for (int j = i + d[i]; j <= de[i]; j += d[i]) dp[j] = (dp[j] + dp[i]) % mod;
        } else {
            lz[i][d[i]] = (lz[i][d[i]] + dp[i]) % mod;
        }
        for (int j = 0; j < S; j++) if (i + j <= n) lz[i + j][j] = (lz[i + j][j] + lz[i][j]) % mod;
        ans = (ans + dp[i]) % mod;
    }
    cout << ans << '\n';
}

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