제출 #1179297

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1179297		gyg	Trains (BOI24_trains)	C++20	21 / 100	2095 ms	2632 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 = 1e5 + 5, MD = 1e9 + 7;

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

int md(int x) { return (x + MD) % MD; }
arr<int, N> dp;
void cmp() {
    for (int i = 1; i <= n; i++) {
        if (i == 1) dp[i] = 1;

        if (!d[i]) continue;

        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: 0 / 16
• Subtask 4: 0 / 34
• Subtask 5: 0 / 29