Submission #1028111

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028111		mdn2002	Trains (BOI24_trains)	C++17	100 / 100	176 ms	8272 KiB

Main

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

void solve() {
    int n, sq = sqrt(1e5);
    long long mod = 1e9 + 7, ans = 0;
    cin >> n;
    vector<long long> d(n + 1), x(n + 1);
    vector<long long> dp(n + 1);
    vector<vector<int>> remove(n + 1);
    vector sumdp(sq + 1, vector<long long>(sq + 1));
    dp[1] = 1;

    for (int i = 1; i <= n; i ++) cin >> d[i] >> x[i];
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= sq; j ++) dp[i] = (dp[i] + sumdp[j][i % j]) % mod;
        ans = (ans + dp[i]) % mod;
        if (d[i] > sq) {
            for (int j = i + d[i]; j <= n; j += d[i]) {
                x[i] --;
                dp[j] = (dp[j] + dp[i]) % mod;
                if (x[i] == 0) break;
            }
        }
        else if (d[i]) {
            sumdp[d[i]][i % d[i]] = (sumdp[d[i]][i % d[i]] + dp[i]) % mod;
            long long next = i + x[i] * d[i];
            if (next <= n) remove[next].push_back(i);
        }
        for (auto j : remove[i]) sumdp[d[j]][j % d[j]] = (sumdp[d[j]][j % d[j]] - dp[j] + mod) % mod;
    }
    cout << ans;
}
/*
5
1 3
2 1
1 3
0 10
3 5
*/
int main()
{
    int T = 1;
    for (int I = 0; I < T; I ++){
        solve();
    }
}

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