Submission #1038597

#TimeUsernameProblemLanguageResultExecution timeMemory
1038597fryingducTrains (BOI24_trains)C++17
100 / 100
160 ms140372 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...