Submission #1368053

#	Time	Username	Problem	Language	Result	Execution time	Memory
1368053		ChottuF	Trains (BOI24_trains)	C++20	100 / 100	115 ms	6156 KiB

Main

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

#define int long long

const int B = 300;
const int MOD = 1e9+7;

int act[B+1][B+1];

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> dp(n+1, 0);
    dp[1] = 1;
    int ans = 0;
    vector<pair<int,int>> rm[n+1]; //d, val
    for (int i = 1; i<=n; i++){
        for (auto u : rm[i]){
            //d, i%d
            auto [d, val] = u;
            act[d][i%d] -= val;
            
            act[d][i%d] %= MOD;
            act[d][i%d] += MOD;
            act[d][i%d] %= MOD;
        }
        
        for (int j = 1; j<B; j++){
            dp[i] += act[j][i%j];
            dp[i] %= MOD;
        }
        ans += dp[i];
        ans %= MOD;
        
        int d,x;
        cin >> d >> x;
        if (d == 0) continue;
        
        if (d >= B){
            for (int j = 1; j<=x; j++){
                int nxt = i + (j*d);
                if (nxt <= n){
                    dp[nxt] += dp[i];
                    dp[nxt] %= MOD;
                }
                else{
                    break;
                }
            }
        }
        else{
            act[d][i%d] += dp[i];
            act[d][i%d] %= MOD;
            
            int dii = i + ((x+1)*d);
            if (dii <= n) rm[dii].push_back({d, dp[i]});
        }
    }
    cout << ans << '\n';
    return 0;
}

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