oj.uz

Submission #493728

# Submission time Handle Problem Language Result Execution time Memory
493728 2021-12-12T17:52:44 Z SangTin Brunhilda’s Birthday (BOI13_brunhilda) C++14
0 / 100
 1000 ms 196804 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 + 1;
int p[M], m, dp[N];

struct segtree{
    int Size;
    vector <int> Max;

    void init(int n){
        Size = n;
        Max.assign(n << 2, 0);
    }

    void push_down(int &x, int mid){
        if (Max[x] == 0) return;
        amax(Max[x << 1], Max[x]);
        amax(Max[x << 1 | 1], Max[x] + mid);
        Max[x] = 0;
    }

    void update(int &l, int &r, int &p, int x, int lx, int rx){
        if (r < lx || rx < l) return;
        if (l <= lx && rx <= r){
            amax(Max[x], p + (lx - l));
            return;
        }
        push_down(x, (rx - lx + 1) >> 1);
        int mid = (lx + rx) >> 1;
        update(l, r, p, x << 1, lx, mid);
        update(l, r, p, x << 1 | 1, mid + 1, rx);
    }
    void update(int l, int r, int p){update(l, r, p, 1, 1, Size);}

    int get(int &i, int x, int lx, int rx){
        if (lx == rx) return Max[x];
        push_down(x, (rx - lx + 1) >> 1);
        int mid = (lx + rx) >> 1;
        if (mid < i) return get(i, x << 1 | 1, mid + 1, rx);
        else return get(i, x << 1, lx, mid);
    }
    int get(int i){return get(i, 1, 1, Size);}
}st;

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

    int cur = m, Max = st.get(n);
    int &res = dp[n];
    if (res >= -1) return res;
    if (!Max) return (res = -1);
    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];
    memset(dp, -0x3f);
    queue <int> query;
    int Max = 0;
    while (q--){
        int n; cin >> n;
        query.push(n);
        amax(Max, n);
    }
    st.init(Max);
    for (int i = 1; i <= m; ++i){
        for (int j = p[i]; j <= Max; j += p[i]){
            st.update(j - p[i] + 1, j - 1, 1);
        }
    }
    while (query.size()){
        int n = query.front();
        query.pop();
        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:72:9: warning: unused variable 'cur' [-Wunused-variable]
   72 |     int cur = m, Max = st.get(n);
      |         ^~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 39628 KB Output isn't correct
2 Incorrect 16 ms 39592 KB Output isn't correct
3 Incorrect 18 ms 39556 KB Output isn't correct
4 Incorrect 18 ms 39648 KB Output isn't correct
5 Incorrect 18 ms 39480 KB Output isn't correct
6 Incorrect 17 ms 39628 KB Output isn't correct
7 Incorrect 16 ms 39624 KB Output isn't correct
8 Incorrect 16 ms 39548 KB Output isn't correct
9 Incorrect 16 ms 39372 KB Output isn't correct
10 Incorrect 18 ms 39500 KB Output isn't correct
11 Incorrect 17 ms 39560 KB Output isn't correct
12 Incorrect 15 ms 39388 KB Output isn't correct
13 Incorrect 19 ms 39544 KB Output isn't correct
14 Incorrect 20 ms 39628 KB Output isn't correct
15 Incorrect 17 ms 39512 KB Output isn't correct
16 Incorrect 17 ms 39540 KB Output isn't correct
17 Incorrect 19 ms 39600 KB Output isn't correct
18 Incorrect 20 ms 39696 KB Output isn't correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 997 ms 194324 KB Output isn't correct
2 Incorrect 992 ms 180708 KB Output isn't correct
3 Execution timed out 1099 ms 113448 KB Time limit exceeded
4 Execution timed out 1065 ms 180984 KB Time limit exceeded
5 Execution timed out 1091 ms 80332 KB Time limit exceeded
6 Incorrect 525 ms 93644 KB Output isn't correct
7 Incorrect 975 ms 194356 KB Output isn't correct
8 Incorrect 611 ms 98036 KB Output isn't correct
9 Execution timed out 1092 ms 80408 KB Time limit exceeded
10 Execution timed out 1095 ms 113364 KB Time limit exceeded
11 Execution timed out 1099 ms 196120 KB Time limit exceeded
12 Execution timed out 1065 ms 173152 KB Time limit exceeded
13 Incorrect 772 ms 194684 KB Output isn't correct
14 Execution timed out 1089 ms 181036 KB Time limit exceeded
15 Execution timed out 1088 ms 89640 KB Time limit exceeded
16 Execution timed out 1000 ms 180704 KB Time limit exceeded
17 Execution timed out 1090 ms 193988 KB Time limit exceeded
18 Execution timed out 1095 ms 196388 KB Time limit exceeded

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 196352 KB Time limit exceeded
2 Execution timed out 1098 ms 196184 KB Time limit exceeded
3 Execution timed out 1092 ms 150212 KB Time limit exceeded
4 Execution timed out 1101 ms 196368 KB Time limit exceeded
5 Execution timed out 1101 ms 196740 KB Time limit exceeded
6 Execution timed out 1086 ms 196336 KB Time limit exceeded
7 Execution timed out 1102 ms 150472 KB Time limit exceeded
8 Execution timed out 1099 ms 196288 KB Time limit exceeded
9 Execution timed out 1098 ms 196308 KB Time limit exceeded
10 Execution timed out 1096 ms 196032 KB Time limit exceeded
11 Execution timed out 1100 ms 195996 KB Time limit exceeded
12 Execution timed out 1106 ms 196000 KB Time limit exceeded
13 Execution timed out 1098 ms 119620 KB Time limit exceeded
14 Execution timed out 1100 ms 135196 KB Time limit exceeded
15 Execution timed out 1085 ms 196132 KB Time limit exceeded
16 Execution timed out 1093 ms 196076 KB Time limit exceeded
17 Execution timed out 1096 ms 196164 KB Time limit exceeded
18 Execution timed out 1095 ms 196284 KB Time limit exceeded
19 Execution timed out 1092 ms 196020 KB Time limit exceeded
20 Execution timed out 1095 ms 150312 KB Time limit exceeded
21 Execution timed out 1095 ms 196376 KB Time limit exceeded
22 Execution timed out 1090 ms 196804 KB Time limit exceeded
23 Execution timed out 1094 ms 196524 KB Time limit exceeded
24 Incorrect 876 ms 196664 KB Output isn't correct
25 Execution timed out 1101 ms 196368 KB Time limit exceeded
26 Execution timed out 1069 ms 196420 KB Time limit exceeded
27 Execution timed out 1096 ms 150468 KB Time limit exceeded
28 Execution timed out 1096 ms 196684 KB Time limit exceeded
29 Execution timed out 1095 ms 196700 KB Time limit exceeded
30 Execution timed out 1094 ms 196692 KB Time limit exceeded
31 Execution timed out 1102 ms 196292 KB Time limit exceeded
32 Execution timed out 1096 ms 196292 KB Time limit exceeded
33 Incorrect 544 ms 196520 KB Output isn't correct
34 Execution timed out 1099 ms 150436 KB Time limit exceeded
35 Execution timed out 1091 ms 196408 KB Time limit exceeded
36 Execution timed out 1094 ms 196716 KB Time limit exceeded
37 Execution timed out 1091 ms 196712 KB Time limit exceeded
38 Execution timed out 1103 ms 196332 KB Time limit exceeded
39 Execution timed out 1101 ms 196364 KB Time limit exceeded
40 Execution timed out 1100 ms 196404 KB Time limit exceeded
41 Execution timed out 1098 ms 150472 KB Time limit exceeded
42 Execution timed out 1099 ms 196396 KB Time limit exceeded