Submission #1368193

#TimeUsernameProblemLanguageResultExecution timeMemory
1368193lucaskojimaTrains (BOI24_trains)C++20
16 / 100
127 ms240756 KiB
#include "bits/stdc++.h"

using namespace std;

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

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

  int n; cin >> n;

  vector<int> d(n), x(n);
  for (int i = 0; i < n; i++)
    cin >> d[i] >> x[i];

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

  for (int i = n - 1; i >= 0; i--) {
    dp[i] = 1;

    if (d[i] < K) {
      if (d[i] && x[i]) {
        int lx = i + d[i];
        int rx = i + (x[i] + 1) * d[i];

        if (lx < n)
          dp[i] = (dp[i] + sum[lx][d[i]]) % MOD;
        if (rx < n)
          dp[i] = ((dp[i] - sum[rx][d[i]]) + MOD) % MOD;
      }
    } else {
      for (int j = i + d[i], k = 0; j < n && k < x[i]; j += d[i], k++)
        dp[i] = (dp[i] + dp[j]) % MOD;
    }

    for (int j = 1; j < K; j++) {
      sum[i][j] = dp[i];
      if (i + j < n)
        sum[i][j] = (sum[i][j] + sum[i + j][j]) % 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...