제출 #1368104

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1368104		lucaskojima	Trains (BOI24_trains)	C++20	0 / 100	5 ms	1860 KiB

Main

#include "bits/stdc++.h"

using namespace std;

const int K   = 316;
const int MOD = 1e9 + 7;

int main() {
  ios::sync_with_stdio(0), cin.tie(0);

  int n; cin >> n;

  vector<pair<int, int>> a(n);
  for (auto &[x, y] : a)
    cin >> x >> y;

  vector sum(K, vector<long long>(K));
  vector<long long> dp(n);

  for (int i = n - 1; i >= 0; i--) {
    auto [d, x] = a[i];
    dp[i] = 1;

    if (d < K)
      dp[i] = (dp[i] + sum[d][i % d]) % MOD;
    else {
      for (int j = i + d; j < n; j += d)
        dp[i] = (dp[i] + dp[j]) % MOD;
    }

    for (int k = 1; k < d; k++)
      sum[k][i % k] = (sum[k][i % k] + dp[i]) % MOD;
  }

  cout << dp[0] << '\n';
  return 0;
}

• 서브태스크 1: 0 / 8
• 서브태스크 2: 0 / 13
• 서브태스크 3: 0 / 16
• 서브태스크 4: 0 / 34
• 서브태스크 5: 0 / 29