Submission #714465

#	Time	Username	Problem	Language	Result	Execution time	Memory
714465		Ahmed57	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	100 / 100	738 ms	124196 KiB

brunhilda

#include <bits/stdc++.h>
using namespace std;
int sub[20000001];
int dp[10000001];
int main(){
    int n,q;
    cin>>n>>q;
    map<int,int>mp;
    for(int i= 0;i<n;i++){
        int x;cin>>x;
        mp[x]++;
    }
    for(auto i:mp){
        for(int j= i.first-1;j<=2e7;j+=i.first){
            sub[j] = max(i.first-1,sub[j]);
        }
    }
    for(int i = int(2e7)-1;i>=1;i--)sub[i]=max(sub[i],sub[i+1]-1);
    dp[0]= 0;
    for(int i = 1;i<=1e7;i++){
        dp[i]=(sub[i]==0?1e9:dp[i-sub[i]]+1);
    }
    while(q--){
        int a;
        cin>>a;if(dp[a]>=1e9)cout<<"oo\n";
        else cout<<dp[a]<<"\n";
    }
    return 0;
}
/*
20 10
13 37 13 37 13 37 13 37 13 37 13 37 13 37 13 37 13 37 13 37
13 37 13 37 13 37 13 37 13 37
*/

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