Submission #155744

#	Time	Username	Problem	Language	Result	Execution time	Memory
155744		puppies_and_rainbows	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	100 / 100	352 ms	79736 KiB

brunhilda

#include <bits/stdc++.h>

#pragma GCC optimize("O3")
using namespace std;

int n, q;
int tobest[10000005];
int last[10000005];
int ans[10000005];
bool use2=false;
int ask[100005], p[100005];
int maxsolved=0, maxask=0;
void eras()
{
    for(int i=1; i<=n; i++)
    {
        if(p[i]!=p[i-1])
        {
            // if(p[i]==2)
            // {
            //     use2=true;
            //     continue;
            // }
            for(int j=0; j<=maxask; j+=p[i])
            {
                last[j]=max(last[j], j+p[i]-1);
            }
        }
    }
}

void solve()
{
    int j=0;
    tobest[1]=p[n]-1;
    for(int i=1; i<=10000000; i++)
    {
        if(tobest[i]==0) return;
        j=tobest[i-1]+1;
        for(int k=j; k<=tobest[i]; k++)
        {
            if(k>maxask) return;
            tobest[i+1]=max(tobest[i+1], last[k]);
            // cout<<k<<" "<<i<<endl;
            ans[k]=i;
        }
        // if(use2&&(tobest[i+1]|1)) tobest[i+1]++;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for(int i=1; i<=n; i++)
    {
        cin>>p[i];
    }
    sort(p+1, p+n+1);
    for(int i=1; i<=q; i++)
    {
        cin>>ask[i];
        maxask=max(maxask, ask[i]);
    }
    eras();
    solve();
    // for(int i=0; i<=5; i++)
    // {
    //     cout<<tobest[i]<<endl;
    // }
    for(int i=1; i<=q; i++)
    {
        if(ans[ask[i]]==0) cout<<"oo\n";
        else cout<<ans[ask[i]]<<"\n";
    }
}

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