제출 #1310298

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310298		harryleee	Trains (BOI24_trains)	C++20	37 / 100	68 ms	3540 KiB

Main

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5;
const long long mod = 1e9 + 7;
int n;
long long d[maxn + 1], x[maxn + 1];
bool check3 = true, check4 = true;

namespace sub2{
    long long dp[10001];

    void solve() {
        dp[1] = 1;
        long long res = 0;

        for (int i = 1; i <= n; ++i){
            res = (res + dp[i]) % mod;
            if (d[i] == 0) continue;
            
            for (int j = 1; j <= x[i]; ++j){
                if (i + d[i] * j > n) break;
                dp[i + d[i] * j] = (dp[i + d[i] * j] + dp[i]) % mod;
                
            }
        }
        
        cout << res << '\n';
        return;
    }
}

namespace sub3{
    long long dp[maxn + 1], dif[maxn + 1];

    void solve(){
        long long res = 0;
        dif[1] = 1;
        dif[2] = (-1 + mod) % mod;

        for (int i = 1; i <= n; ++i){
            dp[i] = (dp[i - 1] + dif[i]) % mod;
            res = (res + dp[i]) % mod;

            int st = i + 1, en = i + x[i] + 1;
            if (en > st){
                dif[st] = (dif[st] + dp[i]) % mod;
                if (en <= n)
                    dif[en] = (dif[en] - dp[i] + mod) % mod;
            }
        }
        
        cout << res << '\n';
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i){
        cin >> d[i] >> x[i];

        if (d[i] != 1) check3 = false;
        if (x[i] != 1e9) check4 = false;
    }

    if (n <= 1e4){
        sub2::solve();
    }
    else if (check3){
        sub3::solve();
    }
}

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