Submission #163947

#	Time	Username	Problem	Language	Result	Execution time	Memory
163947		Leonardo_Paes	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	20 / 100	60 ms	1016 KiB

brunhilda

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e4+10, inf = 0x3f3f3f3f;

int n, q, prime[maxn], dp[maxn];

int solve(int pos){
    if(pos <= 0) return 0;
    if(dp[pos]!=-1) return dp[pos];

    int tot = inf;

    for(int i=1; i<=n; i++){
        int aux = pos % prime[i];

        if(aux) tot = min(tot, 1 + solve(pos - aux));
    }

    return dp[pos] = tot;
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

    cin >> n >> q;

    for(int i=1; i<=n; i++) cin >> prime[i];

    memset(dp, -1, sizeof dp);

    while(q--){
        int nj;

        cin >> nj;

        if(solve(nj) != inf) cout << solve(nj) << "\n";
        else cout << "oo\n";
    }

    return 0;
}

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