oj.uz

Submission #154338

# Submission time Handle Problem Language Result Execution time Memory
154338 2019-09-20T19:14:04 Z brcode Brunhilda’s Birthday (BOI13_brunhilda) C++14
100 / 100
 926 ms 159116 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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