Submission #869003

# Submission time Handle Problem Language Result Execution time Memory
869003 2023-11-02T22:42:56 Z bobbilyking Brunhilda’s Birthday (BOI13_brunhilda) C++17
20 / 100
3 ms 1880 KB
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

#include<bits/stdc++.h>
#include<math.h>
using namespace std;

typedef int ll;
typedef long double ld;
typedef pair<ll, ll> pl;

#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = (l); i < r; ++i)

#define NN 10010
#define M 1000000007 // 998244353

ll dp[NN];

ll last_p_dp[NN]; // last multiple of P's dp value
vector<ll> upd[NN]; // this prime gets a new dp value at this step

int main(){
//    freopen("a.in", "r", stdin);
//    freopen("a.out", "w", stdout);

    ios_base::sync_with_stdio(false); cin.tie(0);
    cout << fixed << setprecision(20);
    G(n) G(q)
    map<ll, ll> v; // might tle; replace with map?
    F(i, 0, n) {
        G(p)
        upd[p].push_back(p);
        v[0]++;
    }
    dp[0] = 0;    
    F(i, 1, NN) {
        for (auto x: upd[i]) {
            if (i + x < NN) upd[i+x].push_back(x);
            if (!--v[last_p_dp[x]]) v.erase(last_p_dp[x]);
        }
        dp[i] = (v.size() ? v.begin()->K : NN) + 1;
        for (auto x: upd[i]) {
            last_p_dp[x] = dp[i];
            v[dp[i]]++;
        }
        upd[i].clear();
    }

    while (q--){
        G(x) 
        if (dp[x] >= NN) cout << "oo\n"; else cout << dp[x] << '\n';
    }
    
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 856 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 2 ms 860 KB Output is correct
14 Correct 2 ms 1116 KB Output is correct
15 Correct 1 ms 856 KB Output is correct
16 Correct 1 ms 860 KB Output is correct
17 Correct 2 ms 704 KB Output is correct
18 Correct 2 ms 684 KB Output is correct
# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1372 KB Execution killed with signal 6
2 Runtime error 1 ms 1116 KB Execution killed with signal 11
3 Runtime error 2 ms 1440 KB Execution killed with signal 6
4 Runtime error 2 ms 1372 KB Execution killed with signal 6
5 Runtime error 1 ms 1116 KB Execution killed with signal 11
6 Runtime error 1 ms 1116 KB Execution killed with signal 11
7 Runtime error 2 ms 1372 KB Execution killed with signal 6
8 Runtime error 2 ms 1368 KB Execution killed with signal 6
9 Runtime error 3 ms 1372 KB Execution killed with signal 6
10 Runtime error 3 ms 1372 KB Execution killed with signal 6
11 Runtime error 2 ms 1372 KB Execution killed with signal 6
12 Runtime error 1 ms 1116 KB Execution killed with signal 11
13 Runtime error 1 ms 1116 KB Execution killed with signal 11
14 Runtime error 2 ms 1372 KB Execution killed with signal 6
15 Runtime error 2 ms 1372 KB Execution killed with signal 6
16 Runtime error 1 ms 1116 KB Execution killed with signal 11
17 Runtime error 1 ms 1116 KB Execution killed with signal 11
18 Runtime error 2 ms 1372 KB Execution killed with signal 6
# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 1116 KB Execution killed with signal 11
2 Runtime error 2 ms 1372 KB Execution killed with signal 6
3 Runtime error 3 ms 1372 KB Execution killed with signal 6
4 Runtime error 1 ms 1116 KB Execution killed with signal 11
5 Runtime error 2 ms 1372 KB Execution killed with signal 6
6 Runtime error 2 ms 1372 KB Execution killed with signal 6
7 Runtime error 2 ms 1372 KB Execution killed with signal 6
8 Runtime error 1 ms 1116 KB Execution killed with signal 11
9 Runtime error 1 ms 1116 KB Execution killed with signal 11
10 Runtime error 1 ms 1116 KB Execution killed with signal 11
11 Runtime error 2 ms 1372 KB Execution killed with signal 6
12 Runtime error 1 ms 1116 KB Execution killed with signal 11
13 Runtime error 2 ms 1372 KB Execution killed with signal 6
14 Runtime error 2 ms 1668 KB Execution killed with signal 11
15 Runtime error 1 ms 1116 KB Execution killed with signal 11
16 Runtime error 2 ms 1372 KB Execution killed with signal 6
17 Runtime error 1 ms 1116 KB Execution killed with signal 11
18 Runtime error 2 ms 1372 KB Execution killed with signal 6
19 Runtime error 1 ms 1116 KB Execution killed with signal 11
20 Runtime error 2 ms 1368 KB Execution killed with signal 6
21 Runtime error 2 ms 1880 KB Execution killed with signal 11
22 Runtime error 2 ms 1372 KB Execution killed with signal 6
23 Runtime error 1 ms 1116 KB Execution killed with signal 11
24 Runtime error 3 ms 1624 KB Execution killed with signal 6
25 Runtime error 1 ms 1116 KB Execution killed with signal 11
26 Runtime error 1 ms 1116 KB Execution killed with signal 11
27 Runtime error 3 ms 1372 KB Execution killed with signal 6
28 Runtime error 1 ms 1112 KB Execution killed with signal 11
29 Runtime error 3 ms 1372 KB Execution killed with signal 6
30 Runtime error 3 ms 1372 KB Execution killed with signal 6
31 Runtime error 1 ms 1116 KB Execution killed with signal 11
32 Runtime error 2 ms 1372 KB Execution killed with signal 6
33 Runtime error 1 ms 1116 KB Execution killed with signal 11
34 Runtime error 2 ms 1400 KB Execution killed with signal 6
35 Runtime error 1 ms 1116 KB Execution killed with signal 11
36 Runtime error 2 ms 1372 KB Execution killed with signal 6
37 Runtime error 2 ms 1384 KB Execution killed with signal 6
38 Runtime error 2 ms 1384 KB Execution killed with signal 6
39 Runtime error 2 ms 1384 KB Execution killed with signal 6
40 Runtime error 1 ms 1128 KB Execution killed with signal 11
41 Runtime error 1 ms 1128 KB Execution killed with signal 11
42 Runtime error 3 ms 1384 KB Execution killed with signal 6