oj.uz

Submission #154332

# Submission time Handle Problem Language Result Execution time Memory
154332 2019-09-20T19:07:36 Z brcode Brunhilda’s Birthday (BOI13_brunhilda) C++14
20 / 100
 981 ms 5416 KB 
#include <iostream>

using namespace std;
const int MAXN = 2e5+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 8 ms 1912 KB Output is correct
2 Correct 7 ms 1912 KB Output is correct
3 Correct 5 ms 1912 KB Output is correct
4 Correct 35 ms 1912 KB Output is correct
5 Correct 5 ms 1912 KB Output is correct
6 Correct 8 ms 1908 KB Output is correct
7 Correct 6 ms 1912 KB Output is correct
8 Correct 5 ms 1912 KB Output is correct
9 Correct 6 ms 1916 KB Output is correct
10 Correct 9 ms 1912 KB Output is correct
11 Correct 8 ms 1916 KB Output is correct
12 Correct 5 ms 1912 KB Output is correct
13 Correct 10 ms 1912 KB Output is correct
14 Correct 34 ms 1912 KB Output is correct
15 Correct 6 ms 1912 KB Output is correct
16 Correct 7 ms 1912 KB Output is correct
17 Correct 35 ms 1912 KB Output is correct
18 Correct 35 ms 1912 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 64 ms 4384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 45 ms 4060 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 10 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 35 ms 3960 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 8 ms 3576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 13 ms 3736 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 8 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 46 ms 4216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 44 ms 4088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 28 ms 3960 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 9 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 8 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 9 ms 3576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 29 ms 3832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 62 ms 4344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 10 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 64 ms 4344 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 4216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 34 ms 4088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 35 ms 4088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 11 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 65 ms 4472 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 13 ms 3960 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 68 ms 4508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 33 ms 4092 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 34 ms 4088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 11 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 10 ms 3832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 11 ms 3832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 23 ms 3960 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 9 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 11 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 12 ms 3832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 31 ms 3960 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 36 ms 4188 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 9 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 33 ms 4088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 8 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 62 ms 4604 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 23 ms 3960 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 8 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 10 ms 3836 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 9 ms 3832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 63 ms 4572 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 8 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 63 ms 4488 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 44 ms 4216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 981 ms 5416 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 9 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 8 ms 3832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 64 ms 4600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 8 ms 3576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 58 ms 4472 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 66 ms 4576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 13 ms 3832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 9 ms 3708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 13 ms 3960 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 66 ms 4572 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Runtime error 11 ms 3704 KB Execution killed with signal 11 (could be triggered by violating memory limits)