Submission #1033646

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033646		coldbr3w	Trains (BOI24_trains)	C++17	100 / 100	212 ms	286908 KiB

Main

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

#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
 
const ll N = 2e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 350;
ll d[N], a[N], dp[N], suf[N][block + 10];
ll n;
void sub_trau(){
    dp[1] = 1;
    ll res = 0;
    for(ll i = 2; i <= n;i++){
        for(int j = 1; j <= i - 1;j++){
            if(d[j] == 0) continue;
            if(j + a[j] * d[j] >= i && i % d[j] == j % d[j]) dp[i] = (dp[i] + dp[j]) % mod;
        }
    }
    for(int i = 1; i <= n;i++) res = (res + dp[i]) % mod;
    cout << res << "\n";
}
void sub_full(){
    for(int i = n; i >= 1;i--){
        dp[i] = 1;
        if(d[i] > block){
            for(int j = 1; j <= a[i];j++){
                if(i + d[i] * j > n) break;
                dp[i] = (dp[i] + dp[i + d[i] * j]) % mod;
            }
        }
        if(d[i] <= block && d[i] > 0 && a[i] > 0) {
            dp[i] = (dp[i] + suf[i + d[i]][d[i]]) % mod;
            if(i + (a[i] + 1) * d[i] <= n) dp[i] = (dp[i] - suf[i + (a[i] + 1) * d[i]][d[i]]) % mod;
        }
        dp[i] = (dp[i] + mod) % mod;
        for(int j = 1; j <= block;j++){
            suf[i][j] = (dp[i] + suf[i + j][j]) % mod;
        }
    }
    cout << dp[1] << "\n";
}
void to_thic_cau(){
    cin >> n;
    for(int i = 1; i <= n;i++) cin >> d[i] >> a[i];
    sub_full();
}
 
signed main(){
    //freopen("A.inp", "r", stdin);
    //freopen("A.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll tc = 1;
    //cin >> tc;
    while(tc--) to_thic_cau();
}

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