Submission #1118572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118572		dynam1c	Trains (BOI24_trains)	C++17	16 / 100	52 ms	4920 KiB

Main

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

  for (int i = 0; i < n; i++) {
    int d, x;
    cin >> d >> x;
    int r = min(x+i, n);
    ends[r].push_back(i);
  }

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

    cur = (cur + ans[i]) % mod;
    for (auto j : ends[i])
      cur = (cur - ans[j] + mod) % mod;
  }

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

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