Submission #1118577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118577		dynam1c	Trains (BOI24_trains)	C++17	0 / 100	36 ms	2344 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int mod = 1e9+7;
int main() {
  int n;
  cin >> n;
  vector<int> x(n), ans(n);
  ans[0] = 1;
  for (int i = 0; i < n; i++)
    cin >> x[i] >> x[i];

  vector<int> diff(n+1);
  int cur = 0;
  for (int i = 0; i < n; i++) {
    if (i > 0)
      ans[i] = cur;

    cur = ((ll) cur + ans[i] + diff[i]) % mod;
    (diff[min(i+x[i], n)] += mod - ans[i]) %= mod;
  }

  cout << accumulate(ans.begin(), ans.end(), 0LL) % mod << endl;
}

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