Submission #1367315

#	Time	Username	Problem	Language	Result	Execution time	Memory
1367315		lucaskojima	Trains (BOI24_trains)	C++20	21 / 100	2095 ms	1988 KiB

Main

#include "bits/stdc++.h"

using namespace std;

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 &[d, x] : a)
    cin >> d >> x;

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

    int cnt = 0;
    for (int j = i + d; j < n; j += d) {
      if (cnt++ == x) break;
      dp[i] = (dp[i] + dp[j]) % MOD;
    }
  }

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

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