답안 #44872

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
44872	2018-04-08T20:26:36 Z	iletavcioski	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	100 / 100	548 ms	117732 KB

brunhilda

#include <iostream>
#include <queue>
using namespace std;
int dp_max[10000001];
int dp[10000001];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int n,q;
    cin>>n>>q;
    for(int i=0;i<n;i++)
    {
        int a;
        cin>>a;
        for(int j=a;j-1<=10000000;j+=a)
        {
            dp_max[j-1]=a-1;
        }
        dp_max[10000000]=max(dp_max[10000000],10000000%a);
    }
    for(int i=9999999;i>=1;i--)
        dp_max[i]=max(dp_max[i],dp_max[i+1]-1);
    for(int i=1;i<=10000000;i++)
    {
        if(dp[i-dp_max[i]]==-1||dp_max[i]==0)
            dp[i]=-1;
        else
            dp[i]=dp[i-dp_max[i]]+1;
    }
    for(int i=0;i<q;i++)
    {
        int a;
        cin>>a;
        if(dp[a]==-1)
            cout<<"oo"<<"\n";
        else
            cout<<dp[a]<<"\n";
    }
    return 0;
}

Subtask #1

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	90 ms	78712 KB	Output is correct
2	Correct	116 ms	78712 KB	Output is correct
3	Correct	106 ms	78788 KB	Output is correct
4	Correct	105 ms	78984 KB	Output is correct
5	Correct	114 ms	78984 KB	Output is correct
6	Correct	87 ms	78984 KB	Output is correct
7	Correct	97 ms	78984 KB	Output is correct
8	Correct	106 ms	78984 KB	Output is correct
9	Correct	144 ms	78984 KB	Output is correct
10	Correct	162 ms	78984 KB	Output is correct
11	Correct	149 ms	79032 KB	Output is correct
12	Correct	91 ms	79092 KB	Output is correct
13	Correct	282 ms	79144 KB	Output is correct
14	Correct	296 ms	79204 KB	Output is correct
15	Correct	135 ms	79204 KB	Output is correct
16	Correct	123 ms	79204 KB	Output is correct
17	Correct	143 ms	79348 KB	Output is correct
18	Correct	117 ms	79348 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	117 ms	79372 KB	Output is correct
2	Correct	140 ms	80096 KB	Output is correct
3	Correct	374 ms	80564 KB	Output is correct
4	Correct	145 ms	80564 KB	Output is correct
5	Correct	245 ms	80928 KB	Output is correct
6	Correct	118 ms	80928 KB	Output is correct
7	Correct	117 ms	80976 KB	Output is correct
8	Correct	157 ms	80992 KB	Output is correct
9	Correct	308 ms	81480 KB	Output is correct
10	Correct	379 ms	81976 KB	Output is correct
11	Correct	373 ms	82264 KB	Output is correct
12	Correct	190 ms	82264 KB	Output is correct
13	Correct	106 ms	82264 KB	Output is correct
14	Correct	144 ms	82264 KB	Output is correct
15	Correct	310 ms	82560 KB	Output is correct
16	Correct	140 ms	83332 KB	Output is correct
17	Correct	310 ms	83332 KB	Output is correct
18	Correct	299 ms	84060 KB	Output is correct

Subtask #3

60.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	353 ms	84816 KB	Output is correct
2	Correct	415 ms	85204 KB	Output is correct
3	Correct	458 ms	86188 KB	Output is correct
4	Correct	347 ms	86892 KB	Output is correct
5	Correct	314 ms	88460 KB	Output is correct
6	Correct	443 ms	89324 KB	Output is correct
7	Correct	368 ms	90488 KB	Output is correct
8	Correct	351 ms	90868 KB	Output is correct
9	Correct	350 ms	91608 KB	Output is correct
10	Correct	255 ms	91688 KB	Output is correct
11	Correct	226 ms	91940 KB	Output is correct
12	Correct	314 ms	92140 KB	Output is correct
13	Correct	476 ms	93236 KB	Output is correct
14	Correct	324 ms	94276 KB	Output is correct
15	Correct	312 ms	94276 KB	Output is correct
16	Correct	364 ms	94276 KB	Output is correct
17	Correct	299 ms	94508 KB	Output is correct
18	Correct	405 ms	95148 KB	Output is correct
19	Correct	143 ms	95360 KB	Output is correct
20	Correct	451 ms	96228 KB	Output is correct
21	Correct	378 ms	97376 KB	Output is correct
22	Correct	531 ms	98496 KB	Output is correct
23	Correct	329 ms	99540 KB	Output is correct
24	Correct	271 ms	100380 KB	Output is correct
25	Correct	384 ms	101236 KB	Output is correct
26	Correct	341 ms	101592 KB	Output is correct
27	Correct	478 ms	102672 KB	Output is correct
28	Correct	276 ms	103668 KB	Output is correct
29	Correct	524 ms	104952 KB	Output is correct
30	Correct	473 ms	106344 KB	Output is correct
31	Correct	288 ms	107048 KB	Output is correct
32	Correct	310 ms	107812 KB	Output is correct
33	Correct	260 ms	108560 KB	Output is correct
34	Correct	349 ms	109580 KB	Output is correct
35	Correct	280 ms	110536 KB	Output is correct
36	Correct	536 ms	111920 KB	Output is correct
37	Correct	350 ms	113328 KB	Output is correct
38	Correct	548 ms	114088 KB	Output is correct
39	Correct	329 ms	114980 KB	Output is correct
40	Correct	488 ms	115644 KB	Output is correct
41	Correct	352 ms	116796 KB	Output is correct
42	Correct	478 ms	117732 KB	Output is correct