Submission #1369518

#TimeUsernameProblemLanguageResultExecution timeMemory
1369518Charizard2021Trains (BOI24_trains)C++20
100 / 100
147 ms163240 KiB
#include<bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
long long B = 200;
int main(){
    long long n;
    cin >> n;
    vector<long long> d(1 + n);
    vector<long long> x(1 + n);
    bool sub4 = true;
    bool sub3 = true;
    for(long long i = 1; i <= n; i++){
        cin >> d[i] >> x[i];
        if(x[i] < n){
            sub4 = false;
        }
        if(d[i] != 1){
            sub3 = false;
        }
    }
    vector<long long> dp(1 + n, 1);
    vector<vector<long long> > sum(1 + n, vector<long long>(B));
    for(long long i = n; i >= 1; i--){
        if(d[i] != 0){
            if(d[i] >= B){
                long long cur = i;
                long long cnt = 0;
                while(cur + d[i] <= n && cnt + 1 <= x[i]){
                    cur += d[i];
                    cnt++;
                    dp[i] = (dp[i] + dp[cur]) % MOD;
                }
            }
            else{
                if(i + d[i] <= n){
                    dp[i] = (dp[i] + sum[i + d[i]][d[i]]) % MOD;
                    long long val = min(n + 1, i + x[i] * d[i] + d[i]);
                    if(val != n + 1){
                        dp[i] = (dp[i] - sum[val][d[i]]) % MOD;
                        if(dp[i] < 0) dp[i] += MOD;
                    }
                }
            }
        }
        for(long long j = 0; j < B; j++){
            if(i + j <= n){
                sum[i][j] = sum[i + j][j];
            }
            sum[i][j] = (sum[i][j] + dp[i]) % MOD;
        }
    }
    cout << dp[1] << "\n";
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...