oj.uz

Submission #757434

# Submission time Handle Problem Language Result Execution time Memory
757434 2023-06-13T07:35:57 Z dxz05 Brunhilda’s Birthday (BOI13_brunhilda) C++17
17.7778 / 100
 1000 ms 1620 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);
        }
    }
 
    for (int i = 1; i < N; i++){
        assert(dp[i] >= dp[i - 1] && dp[i] <= dp[i - 1] + 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:56:13: warning: unused variable 'startTime' [-Wunused-variable]
   56 |     clock_t startTime = clock();
      |             ^~~~~~~~~

Subtask #1
17.7777777778 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 6
2 Correct 4 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 19 ms 428 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Runtime error 2 ms 596 KB Execution killed with signal 6
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 4 ms 332 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 6 ms 328 KB Output is correct
13 Correct 52 ms 364 KB Output is correct
14 Correct 68 ms 408 KB Output is correct
15 Correct 3 ms 340 KB Output is correct
16 Correct 4 ms 328 KB Output is correct
17 Correct 17 ms 416 KB Output is correct
18 Correct 18 ms 416 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 607 ms 616 KB Execution killed with signal 11
2 Execution timed out 1081 ms 1364 KB Time limit exceeded
3 Execution timed out 1059 ms 1108 KB Time limit exceeded
4 Runtime error 151 ms 588 KB Execution killed with signal 11
5 Execution timed out 1071 ms 852 KB Time limit exceeded
6 Runtime error 57 ms 460 KB Execution killed with signal 11
7 Runtime error 588 ms 616 KB Execution killed with signal 11
8 Runtime error 51 ms 500 KB Execution killed with signal 11
9 Execution timed out 1082 ms 1124 KB Time limit exceeded
10 Execution timed out 1067 ms 1108 KB Time limit exceeded
11 Execution timed out 1050 ms 724 KB Time limit exceeded
12 Runtime error 111 ms 488 KB Execution killed with signal 11
13 Runtime error 148 ms 508 KB Execution killed with signal 11
14 Runtime error 157 ms 504 KB Execution killed with signal 11
15 Execution timed out 1049 ms 852 KB Time limit exceeded
16 Execution timed out 1066 ms 1324 KB Time limit exceeded
17 Runtime error 144 ms 500 KB Execution killed with signal 11
18 Execution timed out 1073 ms 1360 KB Time limit exceeded

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1057 ms 980 KB Time limit exceeded
2 Execution timed out 1087 ms 980 KB Time limit exceeded
3 Execution timed out 1082 ms 980 KB Time limit exceeded
4 Runtime error 186 ms 612 KB Execution killed with signal 11
5 Execution timed out 1076 ms 1392 KB Time limit exceeded
6 Runtime error 406 ms 740 KB Execution killed with signal 11
7 Execution timed out 1081 ms 1620 KB Time limit exceeded
8 Execution timed out 1078 ms 980 KB Time limit exceeded
9 Execution timed out 1080 ms 980 KB Time limit exceeded
10 Runtime error 296 ms 608 KB Execution killed with signal 11
11 Runtime error 204 ms 600 KB Execution killed with signal 11
12 Runtime error 307 ms 716 KB Execution killed with signal 11
13 Execution timed out 1079 ms 784 KB Time limit exceeded
14 Runtime error 3 ms 596 KB Execution killed with signal 11
15 Runtime error 252 ms 704 KB Execution killed with signal 11
16 Runtime error 328 ms 708 KB Execution killed with signal 11
17 Execution timed out 1079 ms 852 KB Time limit exceeded
18 Execution timed out 1086 ms 980 KB Time limit exceeded
19 Runtime error 248 ms 604 KB Execution killed with signal 11
20 Execution timed out 1084 ms 972 KB Time limit exceeded
21 Runtime error 7 ms 596 KB Execution killed with signal 11
22 Execution timed out 1069 ms 1600 KB Time limit exceeded
23 Execution timed out 1076 ms 724 KB Time limit exceeded
24 Runtime error 59 ms 524 KB Execution killed with signal 11
25 Runtime error 152 ms 592 KB Execution killed with signal 11
26 Runtime error 182 ms 600 KB Execution killed with signal 11
27 Execution timed out 1075 ms 1604 KB Time limit exceeded
28 Runtime error 49 ms 536 KB Execution killed with signal 11
29 Execution timed out 1086 ms 1620 KB Time limit exceeded
30 Execution timed out 1080 ms 1236 KB Time limit exceeded
31 Runtime error 215 ms 600 KB Execution killed with signal 11
32 Runtime error 136 ms 596 KB Execution killed with signal 11
33 Runtime error 60 ms 524 KB Execution killed with signal 11
34 Execution timed out 1078 ms 1416 KB Time limit exceeded
35 Runtime error 99 ms 592 KB Execution killed with signal 11
36 Execution timed out 1065 ms 1416 KB Time limit exceeded
37 Execution timed out 1068 ms 1360 KB Time limit exceeded
38 Runtime error 429 ms 744 KB Execution killed with signal 11
39 Runtime error 171 ms 596 KB Execution killed with signal 11
40 Runtime error 499 ms 744 KB Execution killed with signal 11
41 Execution timed out 1067 ms 1492 KB Time limit exceeded
42 Runtime error 173 ms 588 KB Execution killed with signal 11