oj.uz

Submission #757385

# Submission time Handle Problem Language Result Execution time Memory
757385 2023-06-13T06:39:11 Z dxz05 Brunhilda’s Birthday (BOI13_brunhilda) C++17
20 / 100
 1000 ms 1748 KB 
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define bpc(x) __builtin_popcount(x)
#define bpcll(x) __builtin_popcountll(x)
#define MP make_pair
//#define endl '\n'

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

typedef long long ll;
const int MOD = 1e9 + 7;
const int N = 1e4 + 2;

int dp[N];

void solve(){
    int m, q;
    cin >> m >> q;

    vector<int> primes(m);
    for (int i = 0; i < m; i++) cin >> primes[i];

    fill(dp + 1, dp + N, 1e9);

    dp[0] = 0;
    for (int i = 1; i < N; i++){
        for (int p : primes){
            dp[i] = min(dp[i], dp[i / p * p] + 1);
        }
    }

    while (q--){
        int i;
        cin >> i;
        if (dp[i] != 1e9){
            cout << dp[i] << "\n";
        } else {
            cout << "oo\n";
        }
    }

}

int main(){
    clock_t startTime = clock();
    ios_base::sync_with_stdio(false);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int test_cases = 1;
//    cin >> test_cases;

    for (int test = 1; test <= test_cases; test++){
        // cout << (solve() ? "YES" : "NO") << endl;
        solve();
    }

#ifdef LOCAL
    cerr << "Time: " << int((double) (clock() - startTime) / CLOCKS_PER_SEC * 1000) << " ms" << endl;
#endif

    return 0;
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:52:13: warning: unused variable 'startTime' [-Wunused-variable]
   52 |     clock_t startTime = clock();
      |             ^~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 18 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 6 ms 324 KB Output is correct
13 Correct 54 ms 336 KB Output is correct
14 Correct 63 ms 404 KB Output is correct
15 Correct 3 ms 324 KB Output is correct
16 Correct 3 ms 340 KB Output is correct
17 Correct 19 ms 424 KB Output is correct
18 Correct 17 ms 420 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 557 ms 604 KB Execution killed with signal 11
2 Execution timed out 1081 ms 1364 KB Time limit exceeded
3 Execution timed out 1074 ms 1108 KB Time limit exceeded
4 Runtime error 149 ms 508 KB Execution killed with signal 11
5 Execution timed out 1088 ms 852 KB Time limit exceeded
6 Runtime error 57 ms 484 KB Execution killed with signal 11
7 Runtime error 555 ms 604 KB Execution killed with signal 11
8 Incorrect 49 ms 340 KB Output isn't correct
9 Execution timed out 1004 ms 1108 KB Time limit exceeded
10 Execution timed out 1071 ms 1116 KB Time limit exceeded
11 Execution timed out 1073 ms 724 KB Time limit exceeded
12 Runtime error 104 ms 500 KB Execution killed with signal 11
13 Runtime error 141 ms 520 KB Execution killed with signal 11
14 Runtime error 144 ms 504 KB Execution killed with signal 11
15 Execution timed out 1063 ms 724 KB Time limit exceeded
16 Execution timed out 1064 ms 1356 KB Time limit exceeded
17 Runtime error 142 ms 504 KB Execution killed with signal 11
18 Execution timed out 1086 ms 1360 KB Time limit exceeded

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1063 ms 1032 KB Time limit exceeded
2 Execution timed out 1071 ms 980 KB Time limit exceeded
3 Execution timed out 1081 ms 980 KB Time limit exceeded
4 Runtime error 160 ms 592 KB Execution killed with signal 11
5 Execution timed out 1084 ms 1736 KB Time limit exceeded
6 Runtime error 408 ms 748 KB Execution killed with signal 11
7 Execution timed out 1052 ms 1620 KB Time limit exceeded
8 Execution timed out 1075 ms 980 KB Time limit exceeded
9 Execution timed out 1062 ms 1028 KB Time limit exceeded
10 Runtime error 295 ms 608 KB Execution killed with signal 11
11 Runtime error 225 ms 612 KB Execution killed with signal 11
12 Runtime error 311 ms 608 KB Execution killed with signal 11
13 Execution timed out 1086 ms 724 KB Time limit exceeded
14 Runtime error 3 ms 596 KB Execution killed with signal 11
15 Runtime error 281 ms 604 KB Execution killed with signal 11
16 Runtime error 333 ms 708 KB Execution killed with signal 11
17 Execution timed out 1071 ms 852 KB Time limit exceeded
18 Execution timed out 1059 ms 980 KB Time limit exceeded
19 Runtime error 252 ms 600 KB Execution killed with signal 11
20 Execution timed out 1085 ms 1028 KB Time limit exceeded
21 Runtime error 7 ms 596 KB Execution killed with signal 11
22 Execution timed out 1083 ms 1620 KB Time limit exceeded
23 Execution timed out 1084 ms 724 KB Time limit exceeded
24 Runtime error 54 ms 520 KB Execution killed with signal 11
25 Runtime error 141 ms 596 KB Execution killed with signal 11
26 Runtime error 168 ms 592 KB Execution killed with signal 11
27 Execution timed out 1071 ms 1612 KB Time limit exceeded
28 Runtime error 48 ms 536 KB Execution killed with signal 11
29 Execution timed out 1080 ms 1620 KB Time limit exceeded
30 Execution timed out 1061 ms 1236 KB Time limit exceeded
31 Runtime error 222 ms 596 KB Execution killed with signal 11
32 Runtime error 142 ms 596 KB Execution killed with signal 11
33 Runtime error 63 ms 584 KB Execution killed with signal 11
34 Execution timed out 1062 ms 1612 KB Time limit exceeded
35 Runtime error 103 ms 592 KB Execution killed with signal 11
36 Execution timed out 1085 ms 1488 KB Time limit exceeded
37 Execution timed out 1064 ms 1736 KB Time limit exceeded
38 Runtime error 406 ms 744 KB Execution killed with signal 11
39 Runtime error 109 ms 604 KB Execution killed with signal 11
40 Runtime error 441 ms 744 KB Execution killed with signal 11
41 Execution timed out 1061 ms 1748 KB Time limit exceeded
42 Runtime error 143 ms 596 KB Execution killed with signal 11