Submission #1125957

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125957		quanquai	Trains (BOI24_trains)	C++20	100 / 100	336 ms	164580 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  
  int n; cin >> n;
  vector<pair<int, int>> a(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> a[i].first >> a[i].second;
  }
  int block_size = 200;
  const int mod = (int) 1e9 + 7;
  vector<int64_t> dp(n + 1, 0);
  vector<vector<int64_t>> diff(block_size + 5, vector<int64_t> (n + 1, 0));
  dp[1] = 1;
  int64_t ans = 0;
  for (int i = 1; i <= n; i++) {
    int d = a[i].first, step = a[i].second;
    int64_t ways = dp[i];
    for (int j = 1; j <= block_size; j++) {
      if (i - j >= 0) diff[j][i] += diff[j][i - j];
      diff[j][i] %= mod;
      ways += diff[j][i];
      ways %= mod;
    }
    ans += ways;
    ans %= mod;
    if (d == 0 || step == 0) continue;
    if (d >= block_size) {
      for (int cur = i + d, j = 1; (cur <= n && j <= step); j++, cur += d) {
        if (cur <= n) dp[cur] += ways, dp[cur] %= mod;  
      }
    } else {
      if (i + d <= n && step > 0) {
        diff[d][i + d] += ways;
        diff[d][i + d] %= mod;
        int last = i + (step + 1) * d;
        if (last <= n) {
          diff[d][last] -= ways;
          diff[d][last] %= mod;
          diff[d][last] += mod;
          diff[d][last] %= mod;
        }
      } 
    }
  }
  cout << ans << '\n';
  return 0;
}

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