oj.uz

Submission #154335

# Submission time Handle Problem Language Result Execution time Memory
154335 2019-09-20T19:10:16 Z brcode Brunhilda’s Birthday (BOI13_brunhilda) C++14
80.3175 / 100
 739 ms 80812 KB 
#include <iostream>

using namespace std;
const int MAXN = 1e7+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 165 ms 78712 KB Output is correct
2 Correct 192 ms 78584 KB Output is correct
3 Correct 167 ms 78712 KB Output is correct
4 Correct 184 ms 78656 KB Output is correct
5 Correct 157 ms 78556 KB Output is correct
6 Correct 157 ms 78664 KB Output is correct
7 Correct 159 ms 78652 KB Output is correct
8 Correct 174 ms 78732 KB Output is correct
9 Correct 202 ms 78752 KB Output is correct
10 Correct 244 ms 78580 KB Output is correct
11 Correct 216 ms 78716 KB Output is correct
12 Correct 145 ms 78588 KB Output is correct
13 Correct 295 ms 78660 KB Output is correct
14 Correct 338 ms 78644 KB Output is correct
15 Correct 180 ms 78712 KB Output is correct
16 Correct 174 ms 78624 KB Output is correct
17 Correct 222 ms 78668 KB Output is correct
18 Correct 191 ms 78712 KB Output is correct

Subtask #2
18.8888888889 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 78872 KB Output is correct
2 Correct 205 ms 79692 KB Output is correct
3 Correct 396 ms 79448 KB Output is correct
4 Correct 187 ms 78584 KB Output is correct
5 Correct 337 ms 79352 KB Output is correct
6 Correct 173 ms 78712 KB Output is correct
7 Correct 187 ms 78756 KB Output is correct
8 Correct 180 ms 78584 KB Output is correct
9 Correct 321 ms 79464 KB Output is correct
10 Correct 375 ms 79340 KB Output is correct
11 Incorrect 377 ms 79096 KB Output isn't correct
12 Correct 222 ms 78584 KB Output is correct
13 Correct 163 ms 78664 KB Output is correct
14 Correct 184 ms 78584 KB Output is correct
15 Correct 323 ms 79036 KB Output is correct
16 Correct 214 ms 79864 KB Output is correct
17 Correct 365 ms 78684 KB Output is correct
18 Correct 384 ms 79864 KB Output is correct

Subtask #3
41.4285714286 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 558 ms 79504 KB Output is correct
2 Correct 522 ms 79480 KB Output is correct
3 Correct 586 ms 79964 KB Output is correct
4 Incorrect 537 ms 79620 KB Output isn't correct
5 Incorrect 565 ms 80724 KB Output isn't correct
6 Correct 626 ms 79600 KB Output is correct
7 Correct 496 ms 80408 KB Output is correct
8 Correct 471 ms 79460 KB Output is correct
9 Correct 491 ms 79472 KB Output is correct
10 Correct 300 ms 78772 KB Output is correct
11 Incorrect 298 ms 79024 KB Output isn't correct
12 Correct 360 ms 78840 KB Output is correct
13 Correct 653 ms 79964 KB Output is correct
14 Correct 526 ms 79956 KB Output is correct
15 Incorrect 380 ms 79020 KB Output isn't correct
16 Correct 394 ms 78840 KB Output is correct
17 Correct 356 ms 79224 KB Output is correct
18 Correct 467 ms 79480 KB Output is correct
19 Incorrect 238 ms 78984 KB Output isn't correct
20 Correct 561 ms 79740 KB Output is correct
21 Incorrect 569 ms 80072 KB Output isn't correct
22 Correct 727 ms 80728 KB Output is correct
23 Correct 530 ms 80128 KB Output is correct
24 Correct 478 ms 79708 KB Output is correct
25 Correct 584 ms 79916 KB Output is correct
26 Incorrect 571 ms 79708 KB Output isn't correct
27 Correct 662 ms 80216 KB Output is correct
28 Incorrect 488 ms 79720 KB Output isn't correct
29 Correct 739 ms 80812 KB Output is correct
30 Correct 683 ms 80340 KB Output is correct
31 Correct 473 ms 79608 KB Output is correct
32 Incorrect 504 ms 79660 KB Output isn't correct
33 Incorrect 450 ms 79480 KB Output isn't correct
34 Correct 488 ms 80428 KB Output is correct
35 Incorrect 528 ms 79768 KB Output isn't correct
36 Correct 717 ms 80644 KB Output is correct
37 Incorrect 559 ms 80760 KB Output isn't correct
38 Correct 622 ms 79864 KB Output is correct
39 Incorrect 502 ms 79720 KB Output isn't correct
40 Correct 573 ms 79684 KB Output is correct
41 Correct 467 ms 80376 KB Output is correct
42 Correct 644 ms 79916 KB Output is correct