oj.uz

Submission #163947

# Submission time Handle Problem Language Result Execution time Memory
163947 2019-11-16T11:29:08 Z Leonardo_Paes Brunhilda’s Birthday (BOI13_brunhilda) C++17
20 / 100
 60 ms 1016 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e4+10, inf = 0x3f3f3f3f;

int n, q, prime[maxn], dp[maxn];

int solve(int pos){
    if(pos <= 0) return 0;
    if(dp[pos]!=-1) return dp[pos];

    int tot = inf;

    for(int i=1; i<=n; i++){
        int aux = pos % prime[i];

        if(aux) tot = min(tot, 1 + solve(pos - aux));
    }

    return dp[pos] = tot;
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

    cin >> n >> q;

    for(int i=1; i<=n; i++) cin >> prime[i];

    memset(dp, -1, sizeof dp);

    while(q--){
        int nj;

        cin >> nj;

        if(solve(nj) != inf) cout << solve(nj) << "\n";
        else cout << "oo\n";
    }

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 9 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 60 ms 508 KB Output is correct
14 Correct 57 ms 504 KB Output is correct
15 Correct 3 ms 376 KB Output is correct
16 Correct 3 ms 376 KB Output is correct
17 Correct 7 ms 392 KB Output is correct
18 Correct 9 ms 504 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 4 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 4 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 4 ms 1012 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 4 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 4 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 4 ms 764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 4 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 3 ms 532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 4 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 4 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 4 ms 888 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 4 ms 764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 4 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 4 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 3 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 4 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 4 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 4 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 4 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 4 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 3 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 3 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 4 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 3 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 4 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 4 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 4 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 3 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 4 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 3 ms 680 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 4 ms 1016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 4 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 3 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 3 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 4 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 4 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 4 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 3 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 4 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 3 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 4 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 4 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 4 ms 892 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 3 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 4 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 4 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)