제출 #1049753

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1049753		NeroZein	Trains (BOI24_trains)	C++17	100 / 100	241 ms	507712 KiB

Main

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

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

const int B = 50;
const int N = 1e5 + 5; 
const int md = (int) 1e9 + 7;

int dp[N];
int d[N], x[N];
int suf[B][B][N];

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

void sub(int& a, int b) {
  a -= b;
  if (a < 0) {
    a += md;
  }
}

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

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