Submission #159758

#	Time	Username	Problem	Language	Result	Execution time	Memory
159758		Rouge_Hugo	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	20 / 100	81 ms	1272 KiB

brunhilda

#include <bits/stdc++.h>

using namespace std;
int n,q;
long long dp[10009];
int a[10009];
long long  d(int x)
{
    if (x==0)return 0;
    if (dp[x]!=-1)return dp[x];
    long long mn=1000000000;
    for(int i=0;i<n;i++)
    {
        if (x%a[i]!=0)mn=min(mn,1+d(x-(x%a[i])));
    }
    return dp[x]=mn;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for(int i=0;i<n;i++)cin>>a[i];
    sort(a,a+n);
    int x;
    memset (dp,-1,sizeof dp);
    while (q--)
    {
        cin>>x;
        long long u=d(x);
        if (u>=1000000)cout<<"oo"<<endl;
        else cout<<u<<endl;

    }

}

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