답안 #154337

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
154337	2019-09-20T19:13:04 Z	brcode	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	92.8571 / 100	1000 ms	159172 KB

brunhilda

#include <iostream>

using namespace std;
const int MAXN = 2e7+5;
int arr[MAXN];
int dp[MAXN];
int dp2[MAXN];
int main(){
  ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    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

#	결과	실행 시간	메모리	Grader output
1	Correct	293 ms	157048 KB	Output is correct
2	Correct	352 ms	157176 KB	Output is correct
3	Correct	353 ms	157176 KB	Output is correct
4	Correct	325 ms	157004 KB	Output is correct
5	Correct	324 ms	157084 KB	Output is correct
6	Correct	296 ms	157028 KB	Output is correct
7	Correct	326 ms	156968 KB	Output is correct
8	Correct	337 ms	156920 KB	Output is correct
9	Correct	393 ms	156944 KB	Output is correct
10	Correct	476 ms	156920 KB	Output is correct
11	Correct	455 ms	157048 KB	Output is correct
12	Correct	317 ms	156836 KB	Output is correct
13	Correct	651 ms	157048 KB	Output is correct
14	Correct	676 ms	156956 KB	Output is correct
15	Correct	377 ms	156920 KB	Output is correct
16	Correct	353 ms	156920 KB	Output is correct
17	Correct	380 ms	157008 KB	Output is correct
18	Correct	350 ms	157048 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	341 ms	157140 KB	Output is correct
2	Correct	371 ms	158004 KB	Output is correct
3	Correct	802 ms	157688 KB	Output is correct
4	Correct	384 ms	156984 KB	Output is correct
5	Correct	567 ms	157560 KB	Output is correct
6	Correct	352 ms	157004 KB	Output is correct
7	Correct	325 ms	157080 KB	Output is correct
8	Correct	381 ms	156956 KB	Output is correct
9	Correct	713 ms	157816 KB	Output is correct
10	Correct	795 ms	157784 KB	Output is correct
11	Correct	763 ms	157432 KB	Output is correct
12	Correct	475 ms	157176 KB	Output is correct
13	Correct	306 ms	156960 KB	Output is correct
14	Correct	418 ms	156892 KB	Output is correct
15	Correct	645 ms	157432 KB	Output is correct
16	Correct	339 ms	157996 KB	Output is correct
17	Correct	718 ms	156976 KB	Output is correct
18	Correct	634 ms	158092 KB	Output is correct

Subtask #3

52.8571428571 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	742 ms	157936 KB	Output is correct
2	Correct	883 ms	157728 KB	Output is correct
3	Correct	972 ms	158072 KB	Output is correct
4	Correct	741 ms	157944 KB	Output is correct
5	Correct	655 ms	159096 KB	Output is correct
6	Correct	947 ms	158072 KB	Output is correct
7	Correct	761 ms	158712 KB	Output is correct
8	Correct	790 ms	157944 KB	Output is correct
9	Correct	764 ms	157956 KB	Output is correct
10	Correct	582 ms	157108 KB	Output is correct
11	Correct	539 ms	157196 KB	Output is correct
12	Correct	681 ms	157220 KB	Output is correct
13	Execution timed out	1052 ms	158192 KB	Time limit exceeded
14	Correct	713 ms	158368 KB	Output is correct
15	Correct	710 ms	157404 KB	Output is correct
16	Correct	769 ms	157176 KB	Output is correct
17	Correct	675 ms	157432 KB	Output is correct
18	Correct	854 ms	157688 KB	Output is correct
19	Correct	379 ms	157176 KB	Output is correct
20	Correct	939 ms	158200 KB	Output is correct
21	Correct	874 ms	158396 KB	Output is correct
22	Execution timed out	1073 ms	159172 KB	Time limit exceeded
23	Correct	659 ms	158328 KB	Output is correct
24	Correct	643 ms	157944 KB	Output is correct
25	Correct	873 ms	157976 KB	Output is correct
26	Correct	737 ms	157844 KB	Output is correct
27	Execution timed out	1047 ms	158584 KB	Time limit exceeded
28	Correct	649 ms	158016 KB	Output is correct
29	Execution timed out	1031 ms	158924 KB	Time limit exceeded
30	Correct	970 ms	158736 KB	Output is correct
31	Correct	622 ms	157816 KB	Output is correct
32	Correct	723 ms	158008 KB	Output is correct
33	Correct	586 ms	157864 KB	Output is correct
34	Correct	826 ms	158600 KB	Output is correct
35	Correct	640 ms	157964 KB	Output is correct
36	Execution timed out	1022 ms	158840 KB	Time limit exceeded
37	Correct	674 ms	159124 KB	Output is correct
38	Correct	943 ms	158080 KB	Output is correct
39	Correct	671 ms	158072 KB	Output is correct
40	Correct	874 ms	158036 KB	Output is correct
41	Correct	653 ms	158580 KB	Output is correct
42	Correct	985 ms	158096 KB	Output is correct