Submission #1368106

#TimeUsernameProblemLanguageResultExecution timeMemory
1368106lucaskojimaTrains (BOI24_trains)C++20
34 / 100
75 ms2756 KiB
#include "bits/stdc++.h"

using namespace std;

const int K   = 316;
const int MOD = 1e9 + 7;

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

  int n; cin >> n;

  vector<pair<int, int>> a(n);
  for (auto &[x, y] : a)
    cin >> x >> y;

  vector sum(K, vector<long long>(K));
  vector<long long> dp(n);

  for (int i = n - 1; i >= 0; i--) {
    auto [d, x] = a[i];
    dp[i] = 1;

    if (d > 0) {
      if (d < K)
        dp[i] = (dp[i] + sum[d][i % d]) % MOD;
      else {
        for (int j = i + d; j < n; j += d)
          dp[i] = (dp[i] + dp[j]) % MOD;
      }
    }

    for (int k = 1; k < K; k++)
      sum[k][i % k] = (sum[k][i % k] + dp[i]) % MOD;
  }

  cout << dp[0] << '\n';
  return 0;
}

#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...