Submission #1195971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195971		LucaLucaM	Brunhilda’s Birthday (BOI13_brunhilda)	C++20	100 / 100	272 ms	118608 KiB

brunhilda

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using ll = long long;
#define debug(x) #x << " = " << x << '\n'

const int VMAX = 1e7;

int to[2 * VMAX + 1];
int dp[VMAX + 1];

int main() {
  #ifdef LOCAL
    freopen("input.txt", "r", stdin);
  #endif
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  int n, q;
  std::cin >> n >> q;

  for (int i = 1; i <= 2 * VMAX; i++) {
    to[i] = VMAX + 1;
  }

  for (int i = 0; i < n; i++) {
    int p;
    std::cin >> p;
    for (int x = 0; x <= VMAX; x += p) {
      to[x + p - 1] = std::min(to[x + p - 1], x);
    }
  }

  
  for (int i = 2 * VMAX - 1; i >= 0; i--) {
    to[i] = std::min(to[i], to[i + 1]);
  }

  for (int i = 1; i <= VMAX; i++) {
    if (to[i] >= i) {
      dp[i] = VMAX + 1;
    } else {
      dp[i] = 1 + dp[to[i]];
    }
  }
  
  while (q--) {
    int x;
    std::cin >> x;
    if (dp[x] <= VMAX) {
      std::cout << dp[x] << '\n';
    } else {
      std::cout << "oo\n";
    }
  }
  
  return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 60 / 60