Submission #1268123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268123		nguyenkhangx	Trains (BOI24_trains)	C++20	100 / 100	111 ms	125312 KiB

Main

#include <bits/stdc++.h>
#define task "a"
using namespace std;
using ll = long long;
const int MOD = 1000000007;

int dp[100009], d[100009], x[100009];
int S[329][100009];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    int N;
    if(!(cin >> N)) return 0;
    for(int i=1;i<=N;i++) cin >> d[i] >> x[i];

    int B = max(1, (int)sqrt(N));

    for(int i=N;i>=1;--i){
        if(d[i] == 0){
            dp[i] = 1;
        } else {
            int dd = d[i];
            int m = min(x[i], (N - i) / dd);
            ll sum = 0;
            if(dd <= B){
                int idx1 = i + dd;
                int idx2 = i + (m + 1) * dd;
                if(idx1 <= N){
                    sum = S[dd][idx1];
                    if(idx2 <= N) sum = (sum - S[dd][idx2] + MOD) % MOD;
                } else sum = 0;
            } else {
                for(int k=1;k<=m;k++){
                    sum += dp[i + k*dd];
                    if(sum >= MOD) sum -= MOD;
                }
            }
            dp[i] = (1 + sum) % MOD;
        }

        // --- FIX: update S[dd][i] for ALL dd = 1..B ---
        for(int dd = 1; dd <= B; ++dd){
            int val = dp[i];
            if(i + dd <= N) {
                val += S[dd][i + dd];
                if(val >= MOD) val -= MOD;
            }
            S[dd][i] = val;
        }
    }

    cout << dp[1] % MOD << '\n';
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:14:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:15:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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