Submission #44318

#	Time	Username	Problem	Language	Result	Execution time	Memory
44318		neutron_byte	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	17.78 / 100	1100 ms	113896 KiB

brunhilda

#include <bits/stdc++.h>
#define INF 1000000000
using namespace std;

const int n = 1000 * 1000;

int main() {
    int m, q, x;
    cin >> m >> q;

    int prime[m];
    for (int i = 0; i < m; ++i) {
        cin >> prime[i];
    }

    int dp[n + 1];
    dp[0] = 0;

    int updated[m];
    fill(updated, updated + m, 0);

    vector<int> current[n + 1];
    for (int i = 0; i < m; ++i) {
        for (int j = 1; prime[i] * j <= n; ++j) {
            current[prime[i] * j].push_back(i);
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int pIdx : current[i]) {
            updated[pIdx] = i;
        }

        int bestVal = INF;
        for (int j = 0; j < m; ++j) {
            bestVal = min(bestVal, updated[j]);
        }

        if (bestVal >= i) dp[i] = INF;
        else dp[i] = 1 + dp[bestVal];
    }

    while (q--) {
        cin >> x;
        cout << (dp[x] < INF ? to_string(dp[x]) : "oo") << endl;
    }

    return 0;
}

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