Submission #1102994

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102994		hqminhuwu	Trains (BOI24_trains)	C++14	100 / 100	97 ms	11664 KiB

Main

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;

#define forr(_a,_b,_c) for(int _a = (_b); _a <= int (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> int (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < int (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

template<class X, class Y>
    bool minz(X &x, const Y &y) {
        if (x > y) {
            x = y;
            return true;
        } return false;
    }
template<class X, class Y>
    bool maxz(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        } return false;
    }

const int N = 2e5 + 5;
const ll oo = (ll) 1e16;
const ll mod = 1e9 + 7; // 998244353;
const int B = 317;

void add (ll &u, ll v){
    u += v;
    if (u >= mod)
        u -= mod;
}

ll n, d[N], x[N];

namespace sub2 {
    ll dp[N];

    void solve(){
        dp[1] = 1;
        ll ans = 0;
    
        forr (i, 1, n){
            if (d[i]){
                for (int j = 1; i + j * d[i] <= n && j <= x[i]; j++){
                    add(dp[i + j * d[i]], dp[i]);
                }
            }
            add(ans, dp[i]);
        }

        cout << ans << "\n";
    }
}

namespace sub4{
    ll dp[N], f[B + 5][B + 5];
    vector <int> dc[N];

    void solve(){
        dp[1] = 1;
        ll ans = 0;
        
        forr (i, 1, n){
            forr (j, 1, B){
                add(dp[i], f[j][i % j]);
            }

            if (d[i] && x[i]){
                if (d[i] > B){
                    for (int j = 1; i + j * d[i] <= n && j <= x[i]; j++){
                        add(dp[i + j * d[i]], dp[i]);
                    }
                } else {
                    add(f[d[i]][i % d[i]], dp[i]);
                    if (i + d[i] * x[i] <= n){
                        dc[i + d[i] * x[i]].pb(i);
                    }
                }
            }

            for (int j : dc[i]){
                add(f[d[j]][j % d[j]], mod - dp[j]);
            }

            add(ans, dp[i]);
        }

        cout << ans << "\n";
    }
}


int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef kaguya
        freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
    #endif

    cin >> n;

    forr (i, 1, n){
        cin >> d[i] >> x[i];
    }

    if (n <= 4000){
        sub2::solve();
    } else {
        sub4::solve();
    }

    return 0;
}
/*



*/

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