Submission #1369517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1369517		Charizard2021	Trains (BOI24_trains)	C++20	71 / 100	2095 ms	83624 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int B = 200;
int main(){
    int n;
    cin >> n;
    vector<int> d(1 + n);
    vector<int> x(1 + n);
    bool sub4 = true;
    bool sub3 = true;
    for(int i = 1; i <= n; i++){
        cin >> d[i] >> x[i];
        if(x[i] < n){
            sub4 = false;
        }
        if(d[i] != 1){
            sub3 = false;
        }
    }
    vector<int> dp(1 + n, 1);
    vector<vector<int> > sum(1 + n, vector<int>(B));
    for(int i = n; i >= 1; i--){
        if(d[i] != 0){
            if(sub4){
                if(d[i] >= B){
                    int cur = i;
                    int 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;
                    }
                }
            }
            else if(sub3){
                if(i != n){
                    int thing = sum[i + 1][1];
                    int val = min(n + 1, i + x[i] + 1);
                    if(val != n + 1){
                        thing = (thing - sum[val][1]) % MOD;
                        if(thing < 0){
                            thing += MOD;
                        }
                    }
                    dp[i] = (dp[i] + thing) % MOD;
                }
            }
            else{
                int cur = i;
                int cnt = 0;
                while(cur + d[i] <= n && cnt + 1 <= x[i]){
                    cur += d[i];
                    cnt++;
                    dp[i] = (dp[i] + dp[cur]) % MOD;
                }
            }
        }
        for(int 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";
}

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