제출 #925229

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
925229		12345678	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	27.62 / 100	2661 ms	262144 KiB

brunhilda

#include <bits/stdc++.h>

using namespace std;

const int nx=2e7+5;
int dp[nx], n, m, x, q, p, res[nx], t, cnt;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>m>>q;
    for (int i=0; i<m; i++)
    {
        cin>>x;
        for (int j=x; j<nx; j+=x) dp[j]=x;
    }
    for (int i=x; i<nx; i++) res[i]=-1;
    for (int i=0; i<x; i++) res[i]=1;
    t=1;
    while (p<nx)
    {
        int mx=x;
        t++;
        for (int i=p; i<x; i++) mx=max(mx, i+dp[i]);
        for (int i=x; i<min(nx-1, mx); i++) res[i]=t;
        if (mx==x) break;
        p=x;
        x=mx;
    }
    //for (int i=0; i<35; i++) cout<<i<<' '<<res[i]<<'\n';
    while (q--)
    {
        cin>>x;
        if (res[x]==-1) cout<<"oo\n";
        else cout<<res[x]<<'\n';
    }
}

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