Submission #1232575

#TimeUsernameProblemLanguageResultExecution timeMemory
1232575asdfgraceTrains (BOI24_trains)C++20
16 / 100
10 ms2632 KiB
#include <bits/stdc++.h>
using namespace std;

#define dbg(x) x
#define prt(x) dbg(cerr << x)
#define pv(x) dbg(cerr << #x << " = " << x << '\n')
#define parr(x) dbg(cerr << #x << " = "; for (auto y : x) {cerr << y << ' ';} cerr << '\n';)
#define parr2d(x) dbg(cerr << #x << " = \n"; for (auto _ : x) {parr(_);} cerr << '\n';)

/*
dp[i] = # of unique paths if you get on the train at i
it's gonna be the sum of all unique paths of stuff that is a multiple of d[i] after i
as long as they are stops
if there are less than sqrt(n) stops, you can add all of them
if d[i] = 1 you could maintain a single suffix sum
if there are more than sqrt(n) stops:
???
there are still o(n) combinations of an interval & a mod, so you can't maintain all of them
actually every element only fits o(sqrt(n)) of them
so just maintain a running suffix thing of these

1
1 2
1 2 3
1 2 4
1 2 5
1 2 4 5
1 2 3 4
1 2 3 5
1 2 3 4 5
*/

const long long mod = 1e9 + 7;

int main() {
  ios::sync_with_stdio(0); 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];
  }
  vector<long long> dp(n, 0), suf(n + 1, 0);
  for (int i = n - 1; i >= 0; i--) {
    dp[i] = (suf[i + 1] + mod - suf[min(n, i + x[i] + 1)] + 1) % mod;
    suf[i] = (dp[i] + suf[i + 1]) % mod;
  }
  cout << dp[0] << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...