oj.uz

Submission #256233

# Submission time Handle Problem Language Result Execution time Memory
256233 2020-08-02T11:45:49 Z shayan_p Brunhilda’s Birthday (BOI13_brunhilda) C++14
11.1111 / 100
 1000 ms 39604 KB 
// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 1e5 + 10, MAX = 1e7 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

int a[maxn], dp[MAX];
set<pii> st;
priority_queue<pii, vector<pii>, greater<pii> > pq;
vector<int> vec;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    int n, q;
    cin >> n >> q;
    int lm = 1;
    for(int i = 0; i < n; i++){
	cin >> a[i];
        lm = min(1ll * lm * a[i], ll(MAX));
	pq.push({0, a[i]});
	st.insert({1, a[i]});
    }
    for(int i = 0; i < lm; i++){
	vec.clear();
	while(!pq.empty() && pq.top().F == i){
	    int p = pq.top().S;
	    vec.PB(p);
	    pq.pop();
	    st.erase({dp[i-p] + 1, p});
	}
	if(i > 0)
	    assert(sz(st)), dp[i] = st.begin()->F;
	for(int x : vec){
	    st.insert({dp[i] + 1, x});
	    pq.push({i + x, x});
	}
    }
    while(q--){
	int x;
	cin >> x;
	if(x >= lm)
	    cout << "oo\n";
	else
	    cout << dp[x] << "\n";
    }
    return 0;
}

Subtask #1
11.1111111111 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Execution timed out 1094 ms 19960 KB Time limit exceeded
3 Correct 29 ms 1400 KB Output is correct
4 Correct 275 ms 39544 KB Output is correct
5 Correct 690 ms 39452 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 30 ms 1400 KB Output is correct
8 Correct 166 ms 3832 KB Output is correct
9 Execution timed out 1072 ms 14596 KB Time limit exceeded
10 Execution timed out 1092 ms 10232 KB Time limit exceeded
11 Execution timed out 1095 ms 16584 KB Time limit exceeded
12 Correct 266 ms 39448 KB Output is correct
13 Execution timed out 1093 ms 5892 KB Time limit exceeded
14 Execution timed out 1095 ms 5720 KB Time limit exceeded
15 Execution timed out 1095 ms 18680 KB Time limit exceeded
16 Execution timed out 1074 ms 19760 KB Time limit exceeded
17 Correct 917 ms 39604 KB Output is correct
18 Correct 280 ms 39588 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 39 ms 11756 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 30 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 4 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 22 ms 6904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 3 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 6 ms 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 3 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 31 ms 9324 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 32 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 19 ms 5496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 3 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 3 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 3 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 18 ms 5744 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 38 ms 11760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 4 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 41 ms 12780 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 6776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 29 ms 7160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 29 ms 6896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 4 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 43 ms 12656 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 8 ms 1664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 45 ms 12784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 24 ms 6792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 23 ms 6896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 5 ms 1280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 4 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 5 ms 1280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 15 ms 4476 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Execution timed out 1095 ms 10456 KB Time limit exceeded
15 Runtime error 5 ms 1384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 5 ms 1408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 25 ms 6168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 23 ms 7152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 4 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 22 ms 6896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Execution timed out 1088 ms 7748 KB Time limit exceeded
22 Runtime error 45 ms 12780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 14 ms 4476 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 4 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 3 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 5 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 49 ms 12780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 3 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 44 ms 12780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 37 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 4 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 3 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 3 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 43 ms 12780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 3 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 40 ms 11632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 44 ms 12652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 6 ms 1664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 4 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 6 ms 1920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 45 ms 12780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Runtime error 4 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)