Submission #997816

#	Time	Username	Problem	Language	Result	Execution time	Memory
997816		jj_master	Trains (BOI24_trains)	C++17	100 / 100	90 ms	6356 KiB

Main

/** Baltic Olympiad in Informatics 2024 **/
 
#include <bits/stdc++.h>
 
using namespace std;
 
const int md = 1e9 + 7;
 
int add(int a, int b) { 
  if (a + b < md) {
    return a + b;
  } else {
    return a + b - md;
  }
}
 
int sub(int a, int b) {
  if (a >= b) {
    return a - b;
  } else {
    return a - b + md;
  }
}
 
void ckadd(int& a, int b) {
  a = add(a, b);
}
 
void cksub(int& a, int b) {
  a = sub(a, b);
}
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> d(n), x(n);
  for (int i = 0; i < n; i++) {
    cin >> d[i] >> x[i];
  }
  const int B = 300;
  vector<int> dp(n);
  dp[0] = 1;
  vector<vector<int>> sum(B, vector<int>(B));
  vector<vector<array<int, 3>>> qs(n + 1);
  for (int i = 0; i < n; i++) {
    for (auto p : qs[i]) {
      cksub(sum[p[0]][p[1]], p[2]);
    }
    for (int j = 1; j < B; j++) {
      ckadd(dp[i], sum[j][i % j]);
    }
    if (d[i] == 0) {
      continue;
    }
    if (d[i] < B) {
      ckadd(sum[d[i]][i % d[i]], dp[i]);
      qs[min((long long) n, i + d[i] * 1ll * x[i] + 1)].push_back({d[i], i % d[i], dp[i]});
    } else {
      for (int j = 1; j <= x[i] && i + j * d[i] < n; j++) {
        ckadd(dp[i + j * d[i]], dp[i]);
      }
    }
  }
  int res = 0;
  for (int i = 0; i < n; i++) {
    ckadd(res, dp[i]);
  }
  cout << res << '\n';
  return 0;
}

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