Submission #1310311

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310311		harryleee	Trains (BOI24_trains)	C++20	100 / 100	130 ms	8128 KiB

Main

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5;
const long long mod = 1e9 + 7;
int n;
long long d[maxn + 1], x[maxn + 1];
bool check3 = true, check4 = true;

namespace sub2{
    long long dp[10001];

    void solve() {
        dp[1] = 1;
        long long res = 0;

        for (int i = 1; i <= n; ++i){
            res = (res + dp[i]) % mod;
            if (d[i] == 0) continue;
            
            for (int j = 1; j <= x[i]; ++j){
                if (i + d[i] * j > n) break;
                dp[i + d[i] * j] = (dp[i + d[i] * j] + dp[i]) % mod;
                
            }
        }
        
        cout << res << '\n';
        return;
    }
}

namespace sub3{
    long long dp[maxn + 1], dif[maxn + 1];

    void solve(){
        long long res = 0;
        dif[1] = 1;
        dif[2] = (-1 + mod) % mod;

        for (int i = 1; i <= n; ++i){
            dp[i] = (dp[i - 1] + dif[i]) % mod;
            res = (res + dp[i]) % mod;

            int st = i + 1, en = i + x[i] + 1;
            if (en > st){
                dif[st] = (dif[st] + dp[i]) % mod;
                if (en <= n)
                    dif[en] = (dif[en] - dp[i] + mod) % mod;
            }
        }
        
        cout << res << '\n';
    }
}

namespace sub4{
    long long dp[maxn + 1], trace[1000][1000];

    void solve(){
        dp[1] = 1;
        long long res = 0;

        for (int i = 1; i <= n; ++i){
            for (int num = 1; num * num <= n; ++num){
                dp[i] = (dp[i] + trace[num][i % num]) % mod;
            }
            res = (res + dp[i]) % mod;

            if (d[i] == 0) continue;

            if (d[i] * d[i] <= n)
                trace[d[i]][i % d[i]] = (trace[d[i]][i % d[i]] + dp[i]) % mod;
            else for (int j = 1; j <= x[i]; ++j){
                if (i + d[i] * j > n) break;
                dp[i + d[i] * j] = (dp[i + d[i] * j] + dp[i]) % mod;   
            }
        }

        cout << res << '\n';
    }
}

namespace sub5{
    long long dp[maxn + 1], trace[101][101];

    struct end_point{
        long long a, b, val;
    }; vector<end_point> expire[maxn + 1];

    void solve(){
        dp[1] = 1;
        long long res = 0;

        for (int i = 1; i <= n; ++i){
            for (auto [a, b, val] : expire[i]){
                trace[a][b] = (trace[a][b] + val + mod) % mod;
            }
            for (int num = 1; num <= 100; ++num){
                dp[i] = (dp[i] + trace[num][i % num]) % mod;
            }
            res = (res + dp[i]) % mod;

            if (d[i] == 0) continue;

            if (d[i] <= 100){
                trace[d[i]][i % d[i]] = (trace[d[i]][i % d[i]] + dp[i]) % mod;
                int end = i + d[i] * (x[i] + 1);
                if (end <= n) 
                    expire[end].push_back({d[i], i % d[i], (-dp[i] + mod) % mod});
            }
            else for (int j = 1; j <= x[i]; ++j){
                if (i + d[i] * j > n) break;
                dp[i + d[i] * j] = (dp[i + d[i] * j] + dp[i]) % mod;   
            }
        }

        cout << res << '\n';
    }
}

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

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

        if (d[i] != 1) check3 = false;
        if (x[i] != 1e9) check4 = false;
    }

    if (n <= 1e4){
        sub2::solve();
    }
    else if (check3){
        sub3::solve();
    }
    else if (check4){
        sub4::solve();
    }
    else{
        sub5::solve();
    }

    return 0;
}

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