Submission #1367310

#TimeUsernameProblemLanguageResultExecution timeMemory
1367310kahoulTrains (BOI24_trains)C++20
58 / 100
58 ms130664 KiB
#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;

int x[maxn];
int d[maxn];

int delm = ceil(sqrt(maxn));

int dp[maxn];
vector<vector<int>> resp(maxn, vector<int>(delm + 2, -1));

int n;

int sum (int a, int b) {
    return (((a + b) % mod) + mod) % mod;
}

int aux(int i, int d) {
    if (d == 0) return 0;
    if (i >= n) return 0;
    if (i == n - 1) return 1;
    if (resp[i][d] != -1) return resp[i][d];
    int ans = sum(dp[i], aux(i + d, d));

    return resp[i][d] = ans;
}

signed main () {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cout.tie(0);
    
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> d[i] >> x[i];
    }

    dp[n - 1] = 1;

    for (int i = n - 2; i >= 0; i--) {
        if (d[i] <= delm) {
            long long thing = (long long)(x[i] + 1) * (long long)(d[i]);

            int t1 = aux(i + d[i], d[i]);
            int t2 = 0; if (i + thing < n) t2 = aux(i + thing, d[i]);
            dp[i] = sum(1 + t1, -t2);
        } else {
            dp[i] = 1;
            for (int j = i + d[i], amt = 1; amt <= x[i]; j += d[i], amt++) {
                dp[i] = sum(dp[i], dp[j]);
            }
        }
    }

    for (int i = 0; i < 1; i++) {
        cout << dp[i] << ' ';
    }
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...