제출 #1367401

#제출 시각아이디문제언어결과실행 시간메모리
1367401lucasdmyTrains (BOI24_trains)C++20
16 / 100
9 ms1860 KiB
#include <bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin>>n;
    vector<pair<int, int>>v(n+10);
    vector<int>dp(n+10, 1), dp_sum(n+10, 0);
    for(int k=1;k<=n;k++){
        cin>>v[k].first>>v[k].second;
    }
    for(int k=n;k>0;k--){
        int at=k+v[k].first, tot=1;
        if(v[k].second==0){
            dp_sum[k]=dp_sum[k+1]+dp[k];
            dp_sum[k]%=MOD;
            continue;
        }
        dp[k]+=dp_sum[k+1]-dp_sum[k+min(v[k].second, n-k)+1];
        dp[k]%=MOD;
        dp[k]+=MOD;
        dp[k]%=MOD;
        dp_sum[k]=dp_sum[k+1]+dp[k];
        dp_sum[k]%=MOD;
    }
    cout<<dp[1];
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…