답안 #154338

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
154338	2019-09-20T19:14:04 Z	brcode	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	100 / 100	926 ms	159116 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"<<"\n";
        }else{
            cout<<dp[x]<<"\n";
        }

    }

}

Subtask #1

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	299 ms	156920 KB	Output is correct
2	Correct	382 ms	157064 KB	Output is correct
3	Correct	346 ms	157132 KB	Output is correct
4	Correct	321 ms	156920 KB	Output is correct
5	Correct	350 ms	156984 KB	Output is correct
6	Correct	292 ms	156920 KB	Output is correct
7	Correct	336 ms	156920 KB	Output is correct
8	Correct	355 ms	157036 KB	Output is correct
9	Correct	397 ms	156944 KB	Output is correct
10	Correct	475 ms	156920 KB	Output is correct
11	Correct	414 ms	156920 KB	Output is correct
12	Correct	287 ms	156920 KB	Output is correct
13	Correct	654 ms	156920 KB	Output is correct
14	Correct	651 ms	156920 KB	Output is correct
15	Correct	366 ms	156920 KB	Output is correct
16	Correct	341 ms	156920 KB	Output is correct
17	Correct	349 ms	156920 KB	Output is correct
18	Correct	291 ms	156920 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	326 ms	157048 KB	Output is correct
2	Correct	336 ms	158032 KB	Output is correct
3	Correct	773 ms	157816 KB	Output is correct
4	Correct	388 ms	156980 KB	Output is correct
5	Correct	554 ms	157532 KB	Output is correct
6	Correct	343 ms	157048 KB	Output is correct
7	Correct	330 ms	157272 KB	Output is correct
8	Correct	379 ms	157048 KB	Output is correct
9	Correct	649 ms	157792 KB	Output is correct
10	Correct	819 ms	157816 KB	Output is correct
11	Correct	836 ms	157560 KB	Output is correct
12	Correct	532 ms	156920 KB	Output is correct
13	Correct	306 ms	156976 KB	Output is correct
14	Correct	384 ms	157084 KB	Output is correct
15	Correct	643 ms	157432 KB	Output is correct
16	Correct	334 ms	158072 KB	Output is correct
17	Correct	694 ms	157008 KB	Output is correct
18	Correct	667 ms	158200 KB	Output is correct

Subtask #3

60.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	749 ms	157856 KB	Output is correct
2	Correct	926 ms	157732 KB	Output is correct
3	Correct	834 ms	158024 KB	Output is correct
4	Correct	557 ms	157832 KB	Output is correct
5	Correct	390 ms	158972 KB	Output is correct
6	Correct	668 ms	158016 KB	Output is correct
7	Correct	583 ms	158716 KB	Output is correct
8	Correct	656 ms	157852 KB	Output is correct
9	Correct	641 ms	157816 KB	Output is correct
10	Correct	552 ms	157048 KB	Output is correct
11	Correct	479 ms	157304 KB	Output is correct
12	Correct	667 ms	157204 KB	Output is correct
13	Correct	836 ms	158276 KB	Output is correct
14	Correct	556 ms	158248 KB	Output is correct
15	Correct	692 ms	157304 KB	Output is correct
16	Correct	715 ms	157252 KB	Output is correct
17	Correct	625 ms	157560 KB	Output is correct
18	Correct	794 ms	157644 KB	Output is correct
19	Correct	321 ms	157176 KB	Output is correct
20	Correct	789 ms	158072 KB	Output is correct
21	Correct	521 ms	158332 KB	Output is correct
22	Correct	795 ms	159116 KB	Output is correct
23	Correct	400 ms	158260 KB	Output is correct
24	Correct	368 ms	157964 KB	Output is correct
25	Correct	557 ms	158040 KB	Output is correct
26	Correct	503 ms	157944 KB	Output is correct
27	Correct	841 ms	158504 KB	Output is correct
28	Correct	350 ms	158072 KB	Output is correct
29	Correct	749 ms	159104 KB	Output is correct
30	Correct	696 ms	158588 KB	Output is correct
31	Correct	406 ms	157836 KB	Output is correct
32	Correct	500 ms	157944 KB	Output is correct
33	Correct	316 ms	157872 KB	Output is correct
34	Correct	588 ms	158596 KB	Output is correct
35	Correct	392 ms	158184 KB	Output is correct
36	Correct	770 ms	158932 KB	Output is correct
37	Correct	391 ms	158992 KB	Output is correct
38	Correct	658 ms	158012 KB	Output is correct
39	Correct	380 ms	158072 KB	Output is correct
40	Correct	578 ms	157992 KB	Output is correct
41	Correct	507 ms	158640 KB	Output is correct
42	Correct	722 ms	158124 KB	Output is correct