Submission #1038597

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038597		fryingduc	Trains (BOI24_trains)	C++17	100 / 100	160 ms	140372 KiB

Main

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

const int maxn = 1e5 + 5;
const int B = 350;
const int mod = 1e9 + 7;
int n, d[maxn], x[maxn];
int f[maxn], g[maxn][B];

int add(int x, int y) {
    if(y < 0) y += mod;
    x = x + y;
    if(x >= mod) x -= mod;
    return x;
}
void solve() {
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> d[i] >> x[i];
    }
    f[1] = 1;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j < B; ++j) {
            if(j < i) g[i][j] = add(g[i][j], g[i - j][j]);
            f[i] = add(f[i], g[i][j]);
        }
        if(d[i] < B) {
            g[i][d[i]] = add(g[i][d[i]], f[i]);
            long long en = 1ll * d[i] * (x[i] + 1) + i;
            if(en <= n) g[en][d[i]] = add(g[en][d[i]], -f[i]);
        }
        else {
            for(int cnt = 1, j = i + d[i]; cnt <= x[i] and j <= n; j += d[i], ++cnt) {
                f[j] = add(f[j], f[i]);
            }
        }
    }
    
    int ans = 0;
    for(int i = 1; i <= n; ++i) {
        ans = add(ans, f[i]);
    }
    cout << ans;
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    solve();
    return 0;
}

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