oj.uz

Submission #1109630

# Submission time Handle Problem Language Result Execution time Memory
1109630 2024-11-07T07:59:10 Z qrn Brunhilda’s Birthday (BOI13_brunhilda) C++14
20 / 100
 1000 ms 1392 KB 
#include <bits/stdc++.h>
using namespace std;

#define SPEED ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);


#define int long long
#define endl "\n"
#define ALL(X) X.begin(), X.end()

const int sz = 10005, inf = 1e9;

vector<int>dp(sz);

void solve() {
    int m, qq;
    cin >> m >> qq;
    vector<int> p(m);
    for(int i = 0; i < m; i++) cin >> p[i];
    dp[0] = 0;
    for(int i = 1; i < sz; i++) dp[i] = inf;
    for(int i = 1; i < sz; i++) {
        int mini = inf;
        for(int j = 0; j < m; j++) {
            mini = min(mini, dp[i - (i % p[j])]);
        }
        dp[i] = mini + 1;   
    }
    while(qq--) {
        int q;
        cin >> q;
        if(dp[q] == inf + 1) {
            cout << "oo" << endl;
        }
        else {
            cout << dp[q] << endl;
        }
    }
}

signed main() {
    SPEED;
    int tst = 1;
    // cin >> tst;
    while(tst--) {
        solve();
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 4 ms 336 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 3 ms 336 KB Output is correct
13 Correct 24 ms 336 KB Output is correct
14 Correct 25 ms 508 KB Output is correct
15 Correct 2 ms 336 KB Output is correct
16 Correct 2 ms 336 KB Output is correct
17 Correct 3 ms 336 KB Output is correct
18 Correct 4 ms 336 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 277 ms 844 KB Execution killed with signal 11
2 Execution timed out 1065 ms 1104 KB Time limit exceeded
3 Execution timed out 1058 ms 848 KB Time limit exceeded
4 Runtime error 73 ms 556 KB Execution killed with signal 11
5 Execution timed out 1067 ms 1020 KB Time limit exceeded
6 Runtime error 31 ms 592 KB Execution killed with signal 11
7 Runtime error 276 ms 872 KB Execution killed with signal 11
8 Runtime error 24 ms 584 KB Execution killed with signal 11
9 Execution timed out 1069 ms 1104 KB Time limit exceeded
10 Execution timed out 1059 ms 848 KB Time limit exceeded
11 Runtime error 927 ms 1352 KB Execution killed with signal 11
12 Runtime error 50 ms 540 KB Execution killed with signal 11
13 Runtime error 69 ms 584 KB Execution killed with signal 11
14 Runtime error 73 ms 552 KB Execution killed with signal 11
15 Runtime error 966 ms 1376 KB Execution killed with signal 11
16 Execution timed out 1060 ms 1104 KB Time limit exceeded
17 Runtime error 70 ms 552 KB Execution killed with signal 11
18 Execution timed out 1055 ms 1104 KB Time limit exceeded

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1053 ms 848 KB Time limit exceeded
2 Execution timed out 1055 ms 848 KB Time limit exceeded
3 Execution timed out 1067 ms 848 KB Time limit exceeded
4 Runtime error 80 ms 552 KB Execution killed with signal 11
5 Execution timed out 1063 ms 1104 KB Time limit exceeded
6 Runtime error 187 ms 840 KB Execution killed with signal 11
7 Execution timed out 1083 ms 1104 KB Time limit exceeded
8 Execution timed out 1062 ms 848 KB Time limit exceeded
9 Execution timed out 1053 ms 848 KB Time limit exceeded
10 Runtime error 136 ms 832 KB Execution killed with signal 11
11 Runtime error 102 ms 584 KB Execution killed with signal 11
12 Runtime error 137 ms 828 KB Execution killed with signal 11
13 Runtime error 700 ms 1016 KB Execution killed with signal 11
14 Runtime error 2 ms 592 KB Execution killed with signal 11
15 Runtime error 128 ms 824 KB Execution killed with signal 11
16 Runtime error 165 ms 836 KB Execution killed with signal 11
17 Execution timed out 1032 ms 1392 KB Time limit exceeded
18 Execution timed out 1051 ms 848 KB Time limit exceeded
19 Runtime error 120 ms 832 KB Execution killed with signal 11
20 Execution timed out 1050 ms 848 KB Time limit exceeded
21 Runtime error 4 ms 592 KB Execution killed with signal 11
22 Execution timed out 1089 ms 1104 KB Time limit exceeded
23 Runtime error 689 ms 1016 KB Execution killed with signal 11
24 Runtime error 28 ms 584 KB Execution killed with signal 11
25 Runtime error 69 ms 584 KB Execution killed with signal 11
26 Runtime error 80 ms 584 KB Execution killed with signal 11
27 Execution timed out 1057 ms 1104 KB Time limit exceeded
28 Runtime error 24 ms 540 KB Execution killed with signal 11
29 Execution timed out 1054 ms 1104 KB Time limit exceeded
30 Execution timed out 1043 ms 848 KB Time limit exceeded
31 Runtime error 102 ms 584 KB Execution killed with signal 11
32 Runtime error 68 ms 584 KB Execution killed with signal 11
33 Runtime error 30 ms 588 KB Execution killed with signal 11
34 Execution timed out 1072 ms 1104 KB Time limit exceeded
35 Runtime error 47 ms 544 KB Execution killed with signal 11
36 Execution timed out 1054 ms 1104 KB Time limit exceeded
37 Execution timed out 1059 ms 1104 KB Time limit exceeded
38 Runtime error 189 ms 836 KB Execution killed with signal 11
39 Runtime error 54 ms 584 KB Execution killed with signal 11
40 Runtime error 217 ms 852 KB Execution killed with signal 11
41 Execution timed out 1070 ms 1104 KB Time limit exceeded
42 Runtime error 70 ms 584 KB Execution killed with signal 11