Submission #1258049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258049		efeg	Trains (BOI24_trains)	C++20	100 / 100	156 ms	8412 KiB

Main

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

#define int long long
#define pb push_back
const int MOD = 1e9 + 7; 

int n; 
vector<int> d,x; 


int32_t main(){
    ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL);
    cin >> n; 
    d.resize(n); x.resize(n);
    for (int i =0 ;i < n; i++) {
        cin >> d[i] >> x[i]; 
    }

    int SIZE = sqrt(n); 

    vector<int> dp(n,0);
    vector<vector<int>> cal(SIZE + 100,vector<int>(SIZE + 100,0)); 
    vector<vector<int>> rm(n+10);  
    dp[0] = 1;  
    int ans = 0; 
    for (int i = 0; i < n; i++){
        for (auto idx : rm[i]){
            cal[d[idx]][idx % d[idx]] = (cal[d[idx]][idx % d[idx]] - dp[idx] + MOD) % MOD; 
        }

        for (int j = 1; j <= SIZE; j++) dp[i] = (dp[i] + cal[j][i % j]) % MOD; 
        
        if (d[i] != 0){
            if (d[i] >= SIZE){
                for (int j = 1; j <= x[i]; j++){
                    int next = i + j * d[i]; 
                    if (next >= n) break; 
                    dp[next] = (dp[next] + dp[i]) % MOD; 
                }
            }
            else {
                cal[d[i]][i % d[i]] = (cal[d[i]][i % d[i]] + dp[i]) % MOD; 
                int zaman = d[i] * x[i] + i + 1; 
                if (zaman > n) zaman = n;
                rm[zaman].pb(i); 
            }
        }

        ans = (ans + dp[i]) % MOD; 
    }

    cout << ans << endl; 


    return 0; 
}

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