Submission #1024066

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024066		serifefedartar	Trains (BOI24_trains)	C++17	100 / 100	196 ms	9244 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define LOGN 61
const ll MOD = 1e9 + 7;
const ll MAXN = 1e5 + 100;

#define int long long
const ll SQ = 400;
vector<int> omit[MAXN];
int classes[400][400], dp[MAXN], d[MAXN], x[MAXN];

signed main() {
    fast
    int N;
    cin >> N;

    dp[1] = 1;
    for (int i = 1; i <= N; i++) {
        for (auto u : omit[i])
            classes[d[u]][u % d[u]] = (classes[d[u]][u % d[u]] - dp[u] + MOD) % MOD;
        for (int m = 1; m < 400; m++)
            dp[i] = (dp[i] + classes[m][i % m]) % MOD;

        cin >> d[i] >> x[i];
        if (d[i] >= SQ) {
            for (int j = i + d[i]; j <= min(N, i + d[i] * x[i]); j += d[i])
                dp[j] = (dp[j] + dp[i]) % MOD;
        } else if (d[i] != 0) {
            classes[d[i]][i % d[i]] = (classes[d[i]][i % d[i]] + dp[i]) % MOD;
            omit[min(N+1, i + d[i] * x[i] + 1)].push_back(i);
        }
    }

    ll ans = 0;
    for (int i = 1; i <= N; i++)
        ans = (ans + dp[i]) % MOD;
    cout << ans << "\n";
}

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