답안 #155744

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
155744	2019-09-30T08:00:57 Z	puppies_and_rainbows	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	100 / 100	352 ms	79736 KB

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.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct
4	Correct	4 ms	504 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	508 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	3 ms	504 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	3 ms	376 KB	Output is correct
14	Correct	4 ms	504 KB	Output is correct
15	Correct	2 ms	508 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	4 ms	504 KB	Output is correct
18	Correct	3 ms	504 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	109 ms	77880 KB	Output is correct
2	Correct	118 ms	71160 KB	Output is correct
3	Correct	115 ms	37568 KB	Output is correct
4	Correct	121 ms	71160 KB	Output is correct
5	Correct	52 ms	20856 KB	Output is correct
6	Correct	48 ms	27512 KB	Output is correct
7	Correct	124 ms	77820 KB	Output is correct
8	Correct	52 ms	29688 KB	Output is correct
9	Correct	52 ms	20984 KB	Output is correct
10	Correct	116 ms	37496 KB	Output is correct
11	Correct	303 ms	78812 KB	Output is correct
12	Correct	146 ms	67320 KB	Output is correct
13	Correct	103 ms	77944 KB	Output is correct
14	Correct	125 ms	71204 KB	Output is correct
15	Correct	60 ms	25592 KB	Output is correct
16	Correct	115 ms	71160 KB	Output is correct
17	Correct	260 ms	77768 KB	Output is correct
18	Correct	265 ms	79072 KB	Output is correct

Subtask #3

60.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	261 ms	79120 KB	Output is correct
2	Correct	312 ms	79012 KB	Output is correct
3	Correct	223 ms	56184 KB	Output is correct
4	Correct	207 ms	79224 KB	Output is correct
5	Correct	158 ms	79608 KB	Output is correct
6	Correct	270 ms	79352 KB	Output is correct
7	Correct	155 ms	56312 KB	Output is correct
8	Correct	296 ms	79060 KB	Output is correct
9	Correct	265 ms	79096 KB	Output is correct
10	Correct	209 ms	78804 KB	Output is correct
11	Correct	183 ms	78892 KB	Output is correct
12	Correct	248 ms	78820 KB	Output is correct
13	Correct	138 ms	40952 KB	Output is correct
14	Correct	110 ms	49180 KB	Output is correct
15	Correct	284 ms	78928 KB	Output is correct
16	Correct	284 ms	78848 KB	Output is correct
17	Correct	287 ms	78840 KB	Output is correct
18	Correct	305 ms	78968 KB	Output is correct
19	Correct	114 ms	78712 KB	Output is correct
20	Correct	191 ms	56156 KB	Output is correct
21	Correct	204 ms	79736 KB	Output is correct
22	Correct	325 ms	79616 KB	Output is correct
23	Correct	164 ms	79448 KB	Output is correct
24	Correct	133 ms	79208 KB	Output is correct
25	Correct	223 ms	79388 KB	Output is correct
26	Correct	207 ms	79356 KB	Output is correct
27	Correct	258 ms	56312 KB	Output is correct
28	Correct	147 ms	79480 KB	Output is correct
29	Correct	305 ms	79664 KB	Output is correct
30	Correct	352 ms	79608 KB	Output is correct
31	Correct	154 ms	79356 KB	Output is correct
32	Correct	167 ms	79224 KB	Output is correct
33	Correct	123 ms	79196 KB	Output is correct
34	Correct	155 ms	56284 KB	Output is correct
35	Correct	151 ms	79364 KB	Output is correct
36	Correct	312 ms	79608 KB	Output is correct
37	Correct	155 ms	79608 KB	Output is correct
38	Correct	273 ms	79356 KB	Output is correct
39	Correct	174 ms	79352 KB	Output is correct
40	Correct	236 ms	79280 KB	Output is correct
41	Correct	147 ms	56292 KB	Output is correct
42	Correct	313 ms	79404 KB	Output is correct