Submission #1097226

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097226		duckindog	Trains (BOI24_trains)	C++17	100 / 100	110 ms	7248 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 100'000 + 10,
          M = 1'000'000'007,
          S = 400;
int n;
int d[N], x[N];

void add(int& x, const int& y) { 
  x += y;
  if (x >= M) x -= M;
};

vector<tuple<int, int, int>> save[N];
int c[S + 10][S + 10];
int f[N];

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> d[i] >> x[i];

  f[1] = 1;
  for (int i = 1; i <= n; ++i) { 
    int& ret = f[i];
    for (const auto& [size, mod, value] : save[i]) add(c[size][mod], M - value);
    for (int j = 1; j <= S; ++j) add(ret, c[j][i % j]);
    
    if (!d[i]) continue;
    
    if (d[i] > S) { 
      for (int j = 1; j <= x[i]; ++j) { 
        int t = i + j * d[i];
        if (t > n) break;
        
        add(f[t], ret);
      }
      continue;
    }
    
    add(c[d[i]][i % d[i]], ret);
    save[min(1ll * n, i + 1ll * d[i] * x[i]) + 1].emplace_back(d[i], i % d[i], ret);
  }

  int answer = 0;
  for (int i = 1; i <= n; ++i) add(answer, f[i]);

  cout << answer << "\n";
}

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