Submission #58741

#	Time	Username	Problem	Language	Result	Execution time	Memory
58741		Batrr	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	100 / 100	790 ms	117988 KiB

brunhilda

#include <bits/stdc++.h>
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
*/
#define ll long long                   
#define f first 
#define s second 
#define pb push_back               
#define mp make_pair 
#define IOS ios_base::sync_with_stdio(0);

using namespace std;                    

const ll maxn=2e5+123,inf=1e18,mod=1e9+7,N=1e7+12,LOG=20;
int n,q,a[maxn],ans[N],cur,pos,nxt,nxtval,mx[N];
int main(){
    #ifdef LOCAL
        freopen ("test.in", "r", stdin);
    #endif
    cin>>n>>q;
    for(int i=0;i<n;i++){
        cin>>a[i];
        for(int j=0;j<N;j+=a[i])
            mx[j]=max(mx[j],a[i]);
    }
    for(int i=0;i<N;i++)
        ans[i]=-1;
    ans[0]=0;
    cur=mx[0];
    pos=1;
    nxt=nxtval=-1;
    while(true){
        while(pos<N && pos%cur!=0){
            ans[pos]=ans[pos/cur*cur]+1;
            if( pos+mx[pos]>nxt )
                nxtval=mx[pos],nxt=pos+mx[pos];
            pos++;
        }
        if(pos==N || nxtval==-1)
            break;
        cur=nxtval;
        nxt=nxtval=-1;
    }
    while(q--){
        int x;
        cin>>x;
        if(ans[x]==-1)            
            cout<<"oo"<<endl;
        else
            cout<<ans[x]<<endl;
    }

}

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