Submission #1188869

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188869		Mher777	Trains (BOI24_trains)	C++20	0 / 100	116 ms	63272 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1'000'000'007;

int addmod(int a, int b) { a += b; if (a >= MOD) a -= MOD; return a; }
int submod(int a, int b) { a -= b; if (a < 0)  a += MOD; return a; }
int mulmod(long long a, long long b) { return int((a * b) % MOD); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> d(N + 2), x(N + 2);
    for (int i = 1; i <= N; ++i) cin >> d[i] >> x[i];

    const int B = int(sqrt(N) + 1);                       
    vector<vector<vector<int>>> pref(B + 1);
    for (int dd = 1; dd <= B; ++dd) {
        pref[dd].resize(dd);
        for (int r = 0; r < dd; ++r) pref[dd][r].push_back(0);
    }

    vector<int> ways(N + 2, 1);    

    for (int i = N; i >= 1; --i) {
        int sum = 0;

        if (d[i] == 0) {
            ways[i] = 1;
        } else if (d[i] <= B) {
            int dd = d[i];
            int r  = i % dd;
            auto &v = pref[dd][r];
            long long cnt = (long long)v.size() - 1; 
            long long k   = min<long long>(x[i], cnt);
            sum = v[k];                      
            ways[i] = addmod(1, sum);
        } else {
            long long cur = i + d[i];
            long long taken = 0;
            while (cur <= N && taken < x[i]) {
                sum = addmod(sum, ways[cur]);
                cur += d[i];
                ++taken;
            }
            ways[i] = addmod(1, sum);
        } 
        for (int dd = 1; dd <= B; ++dd) {
            int r = i % dd;
            auto &v = pref[dd][r];
            v.push_back(addmod(v.back(), ways[i]));
        }
    }

    int answer = 0;
    for (int i = 1; i <= N; ++i) answer = addmod(answer, ways[i]);
    cout << answer << '\n';
    return 0;
}

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