Submission #1049704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049704		NeroZein	Trains (BOI24_trains)	C++17	21 / 100	2097 ms	2908 KiB

Main

#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif

const int md = (int) 1e9 + 7;

void add(int& x, int y) {
  x += y;
  if (x >= md) {
    x -= md; 
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  vector<int> d(n), x(n);
  for (int i = 0; i < n; ++i) {
    cin >> d[i] >> x[i];
  }
  vector<int> dp(n);
  for (int i = n - 1; i >= 0; --i) {
    dp[i] = 1; 
    if (d[i] > 0) {
      for (int j = 1; j <= x[i] && i + d[i] * j < n; ++j) {
        add(dp[i], dp[i + d[i] * j]);
      }      
    }
  }
  cout << dp[0] << '\n';
  return 0;
}

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