oj.uz

Submission #493699

# Submission time Handle Problem Language Result Execution time Memory
493699 2021-12-12T15:32:53 Z SangTin Brunhilda’s Birthday (BOI13_brunhilda) C++14
42.8571 / 100
 1000 ms 41600 KB 
#include <bits/stdc++.h>

using namespace std;

#define name "TRACKS"
#define endl '\n'
#define ednl endl
#define long long long
#define memset(a, x) memset(a, (x), sizeof(a));
#define inoutf freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define IN(a, b, c) (a <= b && b <= c)

template<typename T, typename U> inline bool amin(T &x, U y) { if(y >= x) return 0; x = y; return 1;}
template<typename T, typename U> inline bool amax(T &x, U y) { if(x >= y) return 0; x = y; return 1;}
template<typename T> inline void read(T& x){
    bool Neg = false;
    char c;
    for (c = getchar(); c < '0' | c > '9'; c = getchar())
        if (c == '-') Neg = !Neg;
    x = c - '0';
    for (c = getchar(); c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    if (Neg) x = -x;
}

const int M = 1e5 + 83, N = 1e7 + 83;
int p[M], spf[N], m, dp[N];

int cal(int n){
    if (!n) return 0;

    int cur = m,  Max = 0;
    for (int i = 1; i <= m; ++i){
        if (n % p[i]) amax(Max, n % p[i]);
    }
    int &res = dp[n];
    if (res >= -1) return res;
    if (!Max) return (res = -1);
//    cout << n << ' ' << Max << '\n';
    res = cal(n - Max);
    if (res != -1) ++res;
    return res;
}

int Solve(){
    int q; cin >> m >> q;
    for (int i = 1; i <= m; ++i) cin >> p[i];
    sort(p + 1, p + m + 1);
    memset(dp, -0x3f);
    while (q--){
        int n; cin >> n;
        int tmp = cal(n);
        if (tmp == -1) cout << "oo\n";
        else cout << tmp << endl;
    }

    return 0;
}

int main(){
    fastio;

    int t = 1;
//    cin >> t;
    while (t--){
        Solve();
    }

    return 0;
}

Compilation message

brunhilda.cpp: In function 'int cal(int)':
brunhilda.cpp:33:9: warning: unused variable 'cur' [-Wunused-variable]
   33 |     int cur = m,  Max = 0;
      |         ^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 39372 KB Output is correct
2 Correct 17 ms 39392 KB Output is correct
3 Correct 17 ms 39372 KB Output is correct
4 Correct 22 ms 39480 KB Output is correct
5 Correct 18 ms 39372 KB Output is correct
6 Correct 18 ms 39372 KB Output is correct
7 Correct 16 ms 39356 KB Output is correct
8 Correct 15 ms 39364 KB Output is correct
9 Correct 15 ms 39380 KB Output is correct
10 Correct 16 ms 39372 KB Output is correct
11 Correct 15 ms 39444 KB Output is correct
12 Correct 19 ms 39356 KB Output is correct
13 Correct 23 ms 39340 KB Output is correct
14 Correct 61 ms 39420 KB Output is correct
15 Correct 16 ms 39360 KB Output is correct
16 Correct 16 ms 39372 KB Output is correct
17 Correct 23 ms 39468 KB Output is correct
18 Correct 22 ms 39372 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 39508 KB Output is correct
2 Correct 24 ms 39732 KB Output is correct
3 Correct 22 ms 39720 KB Output is correct
4 Correct 16 ms 39472 KB Output is correct
5 Correct 20 ms 39652 KB Output is correct
6 Correct 17 ms 39420 KB Output is correct
7 Correct 16 ms 39516 KB Output is correct
8 Correct 16 ms 39372 KB Output is correct
9 Correct 22 ms 39672 KB Output is correct
10 Correct 23 ms 39716 KB Output is correct
11 Correct 24 ms 39620 KB Output is correct
12 Correct 18 ms 39372 KB Output is correct
13 Correct 16 ms 39372 KB Output is correct
14 Correct 18 ms 39372 KB Output is correct
15 Correct 20 ms 39628 KB Output is correct
16 Correct 26 ms 39700 KB Output is correct
17 Correct 23 ms 39448 KB Output is correct
18 Correct 28 ms 39828 KB Output is correct

Subtask #3
2.85714285714 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 39628 KB Time limit exceeded
2 Execution timed out 1097 ms 39628 KB Time limit exceeded
3 Execution timed out 1103 ms 39636 KB Time limit exceeded
4 Execution timed out 1065 ms 39632 KB Time limit exceeded
5 Execution timed out 1102 ms 39756 KB Time limit exceeded
6 Execution timed out 1087 ms 39476 KB Time limit exceeded
7 Execution timed out 1096 ms 39884 KB Time limit exceeded
8 Execution timed out 1098 ms 39628 KB Time limit exceeded
9 Execution timed out 1092 ms 39640 KB Time limit exceeded
10 Execution timed out 1089 ms 39720 KB Time limit exceeded
11 Execution timed out 1097 ms 39748 KB Time limit exceeded
12 Execution timed out 1094 ms 39508 KB Time limit exceeded
13 Execution timed out 1089 ms 39624 KB Time limit exceeded
14 Correct 93 ms 41600 KB Output is correct
15 Execution timed out 1082 ms 39476 KB Time limit exceeded
16 Execution timed out 1096 ms 39472 KB Time limit exceeded
17 Execution timed out 1097 ms 39628 KB Time limit exceeded
18 Execution timed out 1090 ms 39628 KB Time limit exceeded
19 Execution timed out 1093 ms 39472 KB Time limit exceeded
20 Execution timed out 1092 ms 39636 KB Time limit exceeded
21 Correct 209 ms 40348 KB Output is correct
22 Execution timed out 1093 ms 39756 KB Time limit exceeded
23 Execution timed out 1096 ms 39500 KB Time limit exceeded
24 Execution timed out 1098 ms 39880 KB Time limit exceeded
25 Execution timed out 1066 ms 39584 KB Time limit exceeded
26 Execution timed out 1090 ms 39616 KB Time limit exceeded
27 Execution timed out 1100 ms 39756 KB Time limit exceeded
28 Execution timed out 1087 ms 39796 KB Time limit exceeded
29 Execution timed out 1097 ms 39756 KB Time limit exceeded
30 Execution timed out 1092 ms 39624 KB Time limit exceeded
31 Execution timed out 1084 ms 39500 KB Time limit exceeded
32 Execution timed out 1098 ms 39620 KB Time limit exceeded
33 Execution timed out 1092 ms 39748 KB Time limit exceeded
34 Execution timed out 1043 ms 39748 KB Time limit exceeded
35 Execution timed out 1094 ms 39748 KB Time limit exceeded
36 Execution timed out 1093 ms 39756 KB Time limit exceeded
37 Execution timed out 1096 ms 39756 KB Time limit exceeded
38 Execution timed out 1098 ms 39472 KB Time limit exceeded
39 Execution timed out 1100 ms 39676 KB Time limit exceeded
40 Execution timed out 1083 ms 39480 KB Time limit exceeded
41 Execution timed out 1086 ms 39828 KB Time limit exceeded
42 Execution timed out 1090 ms 39752 KB Time limit exceeded