Submission #63638

#	Time	Username	Problem	Language	Result	Execution time	Memory
63638		Bodo171	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	100 / 100	803 ms	117788 KiB

brunhilda

#include <iostream>
#include <fstream>

using namespace std;
const int nmax=10*1000*1000+5;
const int nm=10*1000*1000;
int d[nmax],pr[nmax];
int n,m,u,q,i,j,p,x;
int main()
{
    //freopen("data.in","r",stdin);
    cin>>n>>q;
    for(i=1;i<=n;i++)
    {
        cin>>p;
        for(j=p;j<=nm;j+=p)
            pr[j]=p;
    }
    pr[0]=p;
    d[0]=1;
    for(i=0;i<=nm;i++)
        if(d[i])
    {
        for(j=u+1;j<min(i+pr[i],nm+1);j++)
            d[j]=d[i]+1;
        u=max(u,min(i+pr[i],nm+1)-1);
    }
    for(i=1;i<=q;i++)
    {
        cin>>x;
        if(!d[x]) {cout<<"oo\n";continue;}
        cout<<d[x]-1<<'\n';
    }
    return 0;
}

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