Submission #1124055

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124055		adaawf	Brunhilda’s Birthday (BOI13_brunhilda)	C++20	100 / 100	320 ms	79292 KiB

brunhilda

#include <iostream>
using namespace std;
int a[100005], f[10000005], d[10000005], h = 1e7 + 1;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        for (int j = a[i]; j <= h; j += a[i]) f[j - 1] = a[i] - 1;
        f[h] = max(f[h], h % a[i]);
    }
    for (int i = h - 1; i >= 1; i--) {
        f[i] = max(f[i], f[i + 1] - 1);
    }
    for (int i = 1; i <= h; i++) {
        d[i] = 1e9;
        d[i] = min(d[i], d[i - f[i]] + 1);
    }
    for (int jj = 0; jj < q; jj++) {
        int x;
        cin >> x;
        if (d[x] > 1e8) cout << "oo";
        else cout << d[x];
        cout << '\n';
    }
}

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