oj.uz

답안 #154336

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
154336 2019-09-20T19:11:23 Z brcode Brunhilda’s Birthday (BOI13_brunhilda) C++14
87.1429 / 100
 1000 ms 159200 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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