Submission #1258031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258031		efeg	Trains (BOI24_trains)	C++20	50 / 100	142 ms	10012 KiB

Main

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

#define int long long
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<tuple<int,int,int>>> rm(n+10); 
    dp[0] = 1;  
    int ans = 0; 
    for (int i = 0; i < n; i++){
        for (auto tp : rm[i]){
            int i,di,dpi; tie(i,di,dpi) = tp;
            cal[di][i % di] = (cal[di][i % di] - dpi + MOD) % MOD; 
        }

        for (int j = 1; j <= SIZE; j++){
         //   cout << i << " " << j << " "  << i % j << " " << cal[j][i % j] << endl; 
            dp[i] = (dp[i] + cal[j][i % j]) % MOD; 
        }
        
        if (d[i] != 0){
            if (n <= SIZE * d[i]){
                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].emplace_back(i,d[i],dp[i]); 
            }
        }

        ans = (ans + dp[i]) % MOD; 
        //cout << i << ": " << dp[i] << endl;
    }

    cout << ans << endl; 


    return 0; 
}

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