Submission #621415

#	Time	Username	Problem	Language	Result	Execution time	Memory
621415		353cerega	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	100 / 100	387 ms	119812 KiB

brunhilda

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>


using namespace std;


using ll = long long;
using ld = long double;

#define X first
#define Y second

//const ll mod = 1000000007;
const ll mod = 998244353;


const int mx = 10000000;
int dp[mx+1];
int nxt[mx+1];
int g[mx+1];

void solve()
{
    ll m, q;
    cin >> m >> q;
    vector<int> p(m);
    for (ll i=0;i<m;i++) cin >> p[i];
    int mn = mx;
    for (ll i=0;i<m;i++) mn = min(mn,mx/p[i]*p[i]);
    for (int i=0;i<=mx;i++) g[i] = dp[i] = mx;
    for (int i=0;i<m;i++)
    {
        for (int j=p[i];j<=mx;j+=p[i])
        {
            g[j] = min(g[j],j-p[i]);
        }
    }
    for (int i=mx;i>=0;i--)
    {
        nxt[i] = mn;
        mn = min(mn,g[i]);
    }
    dp[0] = 0;
    for (int i=1;i<=mx;i++)
    {
        if (nxt[i]==i) break;
        dp[i] = dp[nxt[i]]+1;
    }
    while (q--)
    {
        ll N;
        cin >> N;
        if (dp[N]<mx) cout << dp[N] << "\n";
        else cout << "oo\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    ll T;
    T = 1;
    //cin >> T;
    while (T--) solve();
}

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