Submission #1349858

#TimeUsernameProblemLanguageResultExecution timeMemory
1349858pandaa73Trains (BOI24_trains)C++20
34 / 100
49 ms28024 KiB
#include <bits/stdc++.h>
using namespace std;

#define ff endl
#define lf "\n"
#define fi first
#define se second
#define _ << ' ' <<
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)

#ifdef DEBUG

constexpr bool IS_DEBUG = 1;

#define infor(fmt, ...) do { print(stderr, fmt, ##__VA_ARGS__); } while(0)
#define infof(fmt, ...) do { println(stderr, fmt, ##__VA_ARGS__); } while(0)

#else

constexpr bool IS_DEBUG = 0;

#define infor(fmt, ...)
#define infof(fmt, ...)

#endif

using ll = long long;

using pll = pair<ll, ll>;
using pii = pair<int, int>;

template<typename... Args>
using vec = vector<Args...>;

constexpr int LOG = 20;
constexpr int MOD = 1e9+7;
constexpr int MAXN = 1e5+7;

mt19937 timmy_loves_gambling(73);

int add(int a, int b) {
    int x = a + b;
    return x < MOD ? x : x - MOD;
}

void chadd(int &a, int b) {
    a = add(a, b);
}

int mul(int a, int b) {
    return (ll)a * b % MOD;
}

void chmul(int &a, int b) {
    a = mul(a, b);
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int N; cin >> N;

    vec<int> K(N), R(N);
    for(int i = 0; i < N; ++i) {
        cin >> K[i] >> R[i];

        if(K[i] >= N - i) K[i] = 0;
        if(K[i] == 0) continue;

        R[i] = min(R[i], (N - i - 1) / K[i]);
    }

    vec<int> dp(N, 1);
    vec<map<int, int>> sfx(2 * N);

    auto calc = [&](int i, int k, int r, auto &&calc) -> int {
        if(i >= r) return 0;

        auto it = sfx[i].find(k);
        if(it != sfx[i].end()) return it->se;

        return sfx[i][k] = add(dp[i], calc(i + k, k, r, calc));
    };

    for(int i = N - 1; i >= 0; i--) {
        if(K[i] == 0) continue;

        int l = i + K[i];
        int r = i + K[i] * (R[i] + 1);

        calc(i + K[i], K[i], r, calc);

        chadd(dp[i], add(sfx[l][K[i]], MOD - sfx[r][K[i]]));
    }

    cout << dp[0] << lf;
}
#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...