Submission #44300

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

brunhilda

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

const int n = 10 * 1000 * 100;

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;

    for (int i = 1; i <= n; ++i) {
        dp[i] = INF;
        for (int j = 0; j < m; ++j) {
            dp[i] = min(dp[i], 1 + dp[i - i % prime[j]]);
        }
    }

    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