제출 #1369508

#제출 시각아이디문제언어결과실행 시간메모리
1369508Charizard2021Trains (BOI24_trains)C++20
34 / 100
88 ms83624 KiB
#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);
    for(int i = 1; i <= n; i++){
        cin >> d[i] >> x[i];
    }
    vector<int> dp(1 + n, 1);
    int pref = 0;
    vector<vector<int> > sum(1 + n, vector<int>(B));
    for(int i = n; i >= 1; i--){
        if(d[i] != 0){
            if(x[i] >= n){
                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(d[i] == 1){
                dp[i] = (dp[i] + pref) % 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;
                }
            }
        }
        pref = (pref + dp[i]) % 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";
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…