oj.uz

Submission #757387

# Submission time Handle Problem Language Result Execution time Memory
757387 2023-06-13T06:40:26 Z dxz05 Brunhilda’s Birthday (BOI13_brunhilda) C++17
20 / 100
 1000 ms 1004 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]);
    }

    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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 16 ms 428 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 340 KB Output is correct
8 Correct 1 ms 332 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 5 ms 340 KB Output is correct
13 Correct 50 ms 340 KB Output is correct
14 Correct 61 ms 408 KB Output is correct
15 Correct 3 ms 340 KB Output is correct
16 Correct 3 ms 340 KB Output is correct
17 Correct 16 ms 428 KB Output is correct
18 Correct 24 ms 416 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 561 ms 604 KB Execution killed with signal 11
2 Execution timed out 1064 ms 940 KB Time limit exceeded
3 Execution timed out 1052 ms 852 KB Time limit exceeded
4 Runtime error 145 ms 588 KB Execution killed with signal 11
5 Execution timed out 1082 ms 724 KB Time limit exceeded
6 Runtime error 58 ms 456 KB Execution killed with signal 11
7 Runtime error 559 ms 604 KB Execution killed with signal 11
8 Runtime error 50 ms 588 KB Execution killed with signal 11
9 Execution timed out 1085 ms 884 KB Time limit exceeded
10 Execution timed out 1069 ms 852 KB Time limit exceeded
11 Execution timed out 1072 ms 756 KB Time limit exceeded
12 Runtime error 98 ms 488 KB Execution killed with signal 11
13 Runtime error 144 ms 512 KB Execution killed with signal 11
14 Runtime error 148 ms 508 KB Execution killed with signal 11
15 Execution timed out 1076 ms 744 KB Time limit exceeded
16 Execution timed out 1070 ms 852 KB Time limit exceeded
17 Runtime error 149 ms 504 KB Execution killed with signal 11
18 Execution timed out 1085 ms 916 KB Time limit exceeded

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1060 ms 724 KB Time limit exceeded
2 Execution timed out 1068 ms 724 KB Time limit exceeded
3 Execution timed out 1025 ms 724 KB Time limit exceeded
4 Runtime error 168 ms 592 KB Execution killed with signal 11
5 Execution timed out 1073 ms 936 KB Time limit exceeded
6 Runtime error 378 ms 748 KB Execution killed with signal 11
7 Execution timed out 1075 ms 876 KB Time limit exceeded
8 Execution timed out 1057 ms 728 KB Time limit exceeded
9 Execution timed out 1061 ms 724 KB Time limit exceeded
10 Runtime error 286 ms 624 KB Execution killed with signal 11
11 Runtime error 213 ms 572 KB Execution killed with signal 11
12 Runtime error 289 ms 608 KB Execution killed with signal 11
13 Execution timed out 1066 ms 712 KB Time limit exceeded
14 Runtime error 3 ms 596 KB Execution killed with signal 11
15 Runtime error 262 ms 612 KB Execution killed with signal 11
16 Runtime error 350 ms 704 KB Execution killed with signal 11
17 Execution timed out 1071 ms 772 KB Time limit exceeded
18 Execution timed out 1059 ms 804 KB Time limit exceeded
19 Runtime error 239 ms 600 KB Execution killed with signal 11
20 Execution timed out 1067 ms 724 KB Time limit exceeded
21 Runtime error 6 ms 596 KB Execution killed with signal 11
22 Execution timed out 1076 ms 1004 KB Time limit exceeded
23 Execution timed out 1076 ms 596 KB Time limit exceeded
24 Runtime error 57 ms 460 KB Execution killed with signal 11
25 Runtime error 140 ms 604 KB Execution killed with signal 11
26 Runtime error 173 ms 596 KB Execution killed with signal 11
27 Execution timed out 1070 ms 976 KB Time limit exceeded
28 Runtime error 47 ms 536 KB Execution killed with signal 11
29 Execution timed out 1070 ms 980 KB Time limit exceeded
30 Execution timed out 1039 ms 852 KB Time limit exceeded
31 Runtime error 218 ms 600 KB Execution killed with signal 11
32 Runtime error 141 ms 600 KB Execution killed with signal 11
33 Runtime error 58 ms 460 KB Execution killed with signal 11
34 Execution timed out 1084 ms 852 KB Time limit exceeded
35 Runtime error 100 ms 592 KB Execution killed with signal 11
36 Execution timed out 1075 ms 812 KB Time limit exceeded
37 Execution timed out 1077 ms 852 KB Time limit exceeded
38 Runtime error 387 ms 544 KB Execution killed with signal 11
39 Runtime error 107 ms 588 KB Execution killed with signal 11
40 Runtime error 435 ms 580 KB Execution killed with signal 11
41 Execution timed out 1081 ms 852 KB Time limit exceeded
42 Runtime error 141 ms 604 KB Execution killed with signal 11