Submission #1195970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195970		LucaLucaM	Brunhilda’s Birthday (BOI13_brunhilda)	C++20	12.54 / 100	460 ms	79144 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[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 <= 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) {
      for (int i = x; i < x + p && x <= VMAX; i++) {
        to[i] = std::min(to[i], x);
      }
    }
  }

  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: 11.1111 / 20
• Subtask 2: 0 / 20
• Subtask 3: 1.4286 / 60