Submission #1310297

#TimeUsernameProblemLanguageResultExecution timeMemory
1310297harryleeeTrains (BOI24_trains)C++20
21 / 100
67 ms2628 KiB
#include<bits/stdc++.h>
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;

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

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

int 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();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...