Submission #1261904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261904		CrabCNH	Trains (BOI24_trains)	C++20	21 / 100	2097 ms	1604 KiB

Main

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

const int N = 1e5 + 5;
const int mod = 1e9 + 7;

int d[N], x[N], dp[N];

int main () {
    ios_base :: sync_with_stdio (0);
    cin.tie (0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        cin >> d[i] >> x[i];
    }
    dp[1] = 1;
    for (int i = 1; i <= n; i ++) {
        if (d[i] == 0) {
            continue;
        }
        for (int t = 1; t <= x[i]; t ++) {
            if (i + t * d[i] > n) {
                break;
            }
            dp[i + t * d[i]] += dp[i];
            dp[i + t * d[i]] %= mod ;
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i ++) {
        //cout << dp[i] << '\n';
        res = (res + dp[i]) % mod;
    }
    cout << res;
}

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