제출 #1033929

#제출 시각아이디문제언어결과실행 시간메모리
1033929trucmaiTrains (BOI24_trains)C++17
100 / 100
194 ms284756 KiB
    #include <bits/stdc++.h>
    #ifdef LOCAL
    #include "/home/trcmai/code/tools.h"
    #define debug(x...)                                                           \
        cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \
        _print(x);                                                                \
        cerr << "\e[39m" << endl;
    #else
    #define debug(x...)
    #endif
    using namespace std;
    #define all(a) a.begin(), a.end()
    #define fi first
    #define se second
    #define ll long long
    #define endl '\n'
    const int N = 2e5 + 6, LOG = 27, MOD = 1e9 + 7;
    const ll INF = 1e18;
    int n;
     
    ll add(ll x, ll y) { return (x + y) % MOD; }
    ll sub(ll x, ll y) { return (x - y % MOD + MOD) % MOD; }
    ll mul(ll x, ll y) { return (x * y) % MOD; }
    void upd(ll& x, ll y) { x = add(x, y); }
    ll dp[N], d[N], x[N];
    const int BS = 350;
    ll sum[N][BS + 10];
    signed main()
    {
        cin.tie(0)->sync_with_stdio(0);
        auto solver = [&]() {
            cin >> n;
            for (int i = 1; i <= n; ++i)
                cin >> d[i] >> x[i];
            for (int i = n; i >= 1; --i) {
                dp[i] = 1;
                if (d[i] > BS) {
                    for (int j = 1; j <= x[i]; ++j) {
                        if (i + d[i] * j > n)
                            break;
                        upd(dp[i], dp[i + d[i]*j]);
                    }
                }
                if (d[i] <= BS && d[i] > 0 && x[i] > 0) {
                    upd(dp[i], sum[i + d[i]][d[i]]);
                    if (i + (x[i] + 1) * d[i] <= n)
                        dp[i] = sub(dp[i], sum[i + (x[i] + 1) * d[i]][d[i]]);
                }
                for (int j = 1; j <= BS; ++j)
                    sum[i][j] = add(sum[i + j][j], dp[i]);
            }
            cout << dp[1] << endl;
        };
        int t = 1; // cin>>t;
        while (t--)
            solver();
    }
#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...