oj.uz

Submission #719877

# Submission time Handle Problem Language Result Execution time Memory
719877 2023-04-07T00:26:00 Z thiago_bastos Brunhilda’s Birthday (BOI13_brunhilda) C++17
56.8254 / 100
 1000 ms 144616 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("mmx,sse,sse2,sse3,sse4,sse4.1,sse4.2,avx")
#include "bits/stdc++.h"

using namespace std;

//#define INF   1000000000
#define INFLL 1000000000000000000ll
#define EPS 1e-9
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define fi first
#define sc second

using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
using ii = pair<int, int>;
using i128 = __int128;

const int N = 1e7 + 10, INF = 0x3f3f3f3f;

int steps[N], maxp[N];

void solve() {
	int m, q;
	priority_queue<ii, vector<ii>, greater<ii>> pq;

	cin >> m >> q;

	memset(steps, 0x3f, sizeof steps);
	
	for(int i = 0; i < m; ++i) {
		int p;
		cin >> p;
		for(int j = 0; j < N; j += p) maxp[j] = p;
	}
	
	pq.emplace(1, maxp[0]);

	for(int i = 1; i < N; ++i) {
		while(!pq.empty() && pq.top().sc <= i) pq.pop();
		if(!pq.empty()) {
			steps[i] = pq.top().fi;
			if(maxp[i]) pq.emplace(steps[i] + 1, i + maxp[i]);
		}
	}

	while(q--) {
		int n;
		cin >> n;
		if(steps[n] == INF) {
			cout << "oo\n";
			continue;
		}
		cout << steps[n] << '\n';
	}
}
 
int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
  	//cin >> t;
	while(t--) solve();
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 78548 KB Output is correct
2 Correct 505 ms 78600 KB Output is correct
3 Correct 64 ms 78472 KB Output is correct
4 Correct 111 ms 78636 KB Output is correct
5 Correct 184 ms 78580 KB Output is correct
6 Correct 52 ms 78592 KB Output is correct
7 Correct 64 ms 78580 KB Output is correct
8 Correct 94 ms 78576 KB Output is correct
9 Correct 437 ms 78580 KB Output is correct
10 Correct 555 ms 78648 KB Output is correct
11 Correct 456 ms 78596 KB Output is correct
12 Correct 91 ms 78588 KB Output is correct
13 Correct 954 ms 78800 KB Output is correct
14 Correct 928 ms 78828 KB Output is correct
15 Correct 508 ms 78588 KB Output is correct
16 Correct 513 ms 78588 KB Output is correct
17 Correct 247 ms 78644 KB Output is correct
18 Correct 102 ms 78548 KB Output is correct

Subtask #2
11.1111111111 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 80864 KB Output is correct
2 Correct 382 ms 95420 KB Output is correct
3 Execution timed out 1087 ms 111840 KB Time limit exceeded
4 Correct 532 ms 79240 KB Output is correct
5 Execution timed out 1069 ms 95420 KB Time limit exceeded
6 Correct 589 ms 79184 KB Output is correct
7 Correct 273 ms 80832 KB Output is correct
8 Correct 412 ms 78856 KB Output is correct
9 Execution timed out 1072 ms 95368 KB Time limit exceeded
10 Execution timed out 1081 ms 111820 KB Time limit exceeded
11 Execution timed out 1071 ms 87192 KB Time limit exceeded
12 Correct 852 ms 79184 KB Output is correct
13 Correct 306 ms 79716 KB Output is correct
14 Correct 507 ms 79208 KB Output is correct
15 Execution timed out 1061 ms 87148 KB Time limit exceeded
16 Correct 377 ms 95336 KB Output is correct
17 Execution timed out 1077 ms 79204 KB Time limit exceeded
18 Execution timed out 1049 ms 144616 KB Time limit exceeded

Subtask #3
25.7142857143 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1049 ms 87148 KB Time limit exceeded
2 Execution timed out 1050 ms 87184 KB Time limit exceeded
3 Execution timed out 1077 ms 87196 KB Time limit exceeded
4 Correct 879 ms 79984 KB Output is correct
5 Correct 449 ms 95276 KB Output is correct
6 Execution timed out 1074 ms 79820 KB Time limit exceeded
7 Execution timed out 1076 ms 95340 KB Time limit exceeded
8 Execution timed out 1085 ms 87132 KB Time limit exceeded
9 Execution timed out 1068 ms 87192 KB Time limit exceeded
10 Correct 888 ms 79776 KB Output is correct
11 Correct 749 ms 79564 KB Output is correct
12 Execution timed out 1029 ms 79776 KB Time limit exceeded
13 Execution timed out 1053 ms 87104 KB Time limit exceeded
14 Correct 598 ms 79436 KB Output is correct
15 Execution timed out 1072 ms 79844 KB Time limit exceeded
16 Execution timed out 1077 ms 79936 KB Time limit exceeded
17 Execution timed out 1085 ms 87156 KB Time limit exceeded
18 Execution timed out 1087 ms 87104 KB Time limit exceeded
19 Correct 465 ms 82884 KB Output is correct
20 Execution timed out 1070 ms 87232 KB Time limit exceeded
21 Correct 739 ms 79380 KB Output is correct
22 Execution timed out 1072 ms 95332 KB Time limit exceeded
23 Correct 469 ms 82768 KB Output is correct
24 Correct 272 ms 79404 KB Output is correct
25 Correct 865 ms 79660 KB Output is correct
26 Correct 889 ms 79884 KB Output is correct
27 Execution timed out 1074 ms 95396 KB Time limit exceeded
28 Correct 411 ms 79816 KB Output is correct
29 Execution timed out 1074 ms 95468 KB Time limit exceeded
30 Execution timed out 1080 ms 87144 KB Time limit exceeded
31 Correct 519 ms 80092 KB Output is correct
32 Correct 592 ms 79572 KB Output is correct
33 Correct 196 ms 79408 KB Output is correct
34 Execution timed out 1082 ms 95476 KB Time limit exceeded
35 Correct 439 ms 79860 KB Output is correct
36 Execution timed out 1063 ms 95348 KB Time limit exceeded
37 Correct 433 ms 95312 KB Output is correct
38 Execution timed out 1074 ms 79748 KB Time limit exceeded
39 Correct 324 ms 79496 KB Output is correct
40 Execution timed out 1066 ms 80752 KB Time limit exceeded
41 Execution timed out 1077 ms 144604 KB Time limit exceeded
42 Execution timed out 1042 ms 79224 KB Time limit exceeded