Submission #154336

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
154336	2019-09-20T19:11:23 Z	brcode	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	87.1429 / 100	1000 ms	159200 KB

brunhilda

#include <iostream>

using namespace std;
const int MAXN = 2e7+5;
int arr[MAXN];
int dp[MAXN];
int dp2[MAXN];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    for(int i=0;i<arr[n];i++){
        dp[i] = 1;
    }
    for(int i=arr[n];i<MAXN;i++){
        dp[i] = 1e9;
    }
    for(int i=1;i<=n;i++){
        for(int j=arr[i]-1;j<MAXN;j+=arr[i]){

            dp2[j] = max(dp2[j],arr[i]-1);
            //cout<<j<<" "<<dp2[j]<<endl;
        }
    }
    for(int i=MAXN-1;i>=0;i--){
        dp2[i] = max(dp2[i],dp2[i+1]-1);
    }
    for(int i=arr[n];i<MAXN;i++){
        dp[i] = min(dp[i],dp[i-dp2[i]]+1);
    }
    for(int i=1;i<=m;i++){
        int x;
        cin>>x;
        if(dp[x]==1e9){
            cout<<"oo"<<endl;
        }else{
            cout<<dp[x]<<endl;
        }

    }

}

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	294 ms	157048 KB	Output is correct
2	Correct	353 ms	156920 KB	Output is correct
3	Correct	315 ms	156920 KB	Output is correct
4	Correct	338 ms	157068 KB	Output is correct
5	Correct	323 ms	156920 KB	Output is correct
6	Correct	293 ms	156860 KB	Output is correct
7	Correct	332 ms	156920 KB	Output is correct
8	Correct	328 ms	157044 KB	Output is correct
9	Correct	372 ms	156920 KB	Output is correct
10	Correct	493 ms	156936 KB	Output is correct
11	Correct	400 ms	156920 KB	Output is correct
12	Correct	288 ms	156992 KB	Output is correct
13	Correct	650 ms	156944 KB	Output is correct
14	Correct	686 ms	157220 KB	Output is correct
15	Correct	422 ms	156920 KB	Output is correct
16	Correct	370 ms	156928 KB	Output is correct
17	Correct	432 ms	156892 KB	Output is correct
18	Correct	353 ms	156920 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	333 ms	157048 KB	Output is correct
2	Correct	384 ms	157944 KB	Output is correct
3	Correct	839 ms	157684 KB	Output is correct
4	Correct	385 ms	156860 KB	Output is correct
5	Correct	595 ms	157600 KB	Output is correct
6	Correct	354 ms	157052 KB	Output is correct
7	Correct	332 ms	157000 KB	Output is correct
8	Correct	418 ms	157048 KB	Output is correct
9	Correct	678 ms	157692 KB	Output is correct
10	Correct	812 ms	157688 KB	Output is correct
11	Correct	782 ms	157432 KB	Output is correct
12	Correct	481 ms	156908 KB	Output is correct
13	Correct	306 ms	157048 KB	Output is correct
14	Correct	396 ms	157048 KB	Output is correct
15	Correct	734 ms	157352 KB	Output is correct
16	Correct	380 ms	158120 KB	Output is correct
17	Correct	680 ms	156972 KB	Output is correct
18	Correct	684 ms	158200 KB	Output is correct

Subtask #3

47.1428571429 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	800 ms	157868 KB	Output is correct
2	Correct	882 ms	157624 KB	Output is correct
3	Execution timed out	1000 ms	158028 KB	Time limit exceeded
4	Correct	791 ms	157916 KB	Output is correct
5	Correct	756 ms	159200 KB	Output is correct
6	Correct	948 ms	158072 KB	Output is correct
7	Correct	852 ms	158624 KB	Output is correct
8	Correct	896 ms	157740 KB	Output is correct
9	Correct	838 ms	157916 KB	Output is correct
10	Correct	659 ms	157092 KB	Output is correct
11	Correct	590 ms	157176 KB	Output is correct
12	Correct	781 ms	157216 KB	Output is correct
13	Execution timed out	1079 ms	158012 KB	Time limit exceeded
14	Correct	831 ms	158328 KB	Output is correct
15	Correct	820 ms	157248 KB	Output is correct
16	Correct	910 ms	157296 KB	Output is correct
17	Correct	843 ms	157532 KB	Output is correct
18	Correct	920 ms	157696 KB	Output is correct
19	Correct	407 ms	157140 KB	Output is correct
20	Execution timed out	1082 ms	158004 KB	Time limit exceeded
21	Correct	865 ms	158328 KB	Output is correct
22	Execution timed out	1078 ms	158840 KB	Time limit exceeded
23	Correct	724 ms	158176 KB	Output is correct
24	Correct	647 ms	157944 KB	Output is correct
25	Correct	856 ms	157992 KB	Output is correct
26	Correct	805 ms	157944 KB	Output is correct
27	Execution timed out	1090 ms	158512 KB	Time limit exceeded
28	Correct	668 ms	158072 KB	Output is correct
29	Execution timed out	1091 ms	158956 KB	Time limit exceeded
30	Execution timed out	1034 ms	158716 KB	Time limit exceeded
31	Correct	678 ms	157820 KB	Output is correct
32	Correct	743 ms	157940 KB	Output is correct
33	Correct	608 ms	157944 KB	Output is correct
34	Correct	842 ms	158588 KB	Output is correct
35	Correct	675 ms	158032 KB	Output is correct
36	Execution timed out	1099 ms	158812 KB	Time limit exceeded
37	Correct	746 ms	159096 KB	Output is correct
38	Correct	978 ms	158072 KB	Output is correct
39	Correct	735 ms	158032 KB	Output is correct
40	Correct	936 ms	158116 KB	Output is correct
41	Correct	756 ms	158680 KB	Output is correct
42	Execution timed out	1036 ms	158068 KB	Time limit exceeded