oj.uz

답안 #719870

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
719870 2023-04-06T23:27:52 Z thiago_bastos Brunhilda’s Birthday (BOI13_brunhilda) C++17
63.6508 / 100
 1000 ms 145388 KB 
#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

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 78540 KB Output is correct
2 Correct 415 ms 78588 KB Output is correct
3 Correct 53 ms 78536 KB Output is correct
4 Correct 90 ms 78636 KB Output is correct
5 Correct 169 ms 78580 KB Output is correct
6 Correct 41 ms 78540 KB Output is correct
7 Correct 53 ms 78576 KB Output is correct
8 Correct 76 ms 78540 KB Output is correct
9 Correct 371 ms 78580 KB Output is correct
10 Correct 433 ms 78588 KB Output is correct
11 Correct 385 ms 78532 KB Output is correct
12 Correct 77 ms 78576 KB Output is correct
13 Correct 785 ms 78792 KB Output is correct
14 Correct 774 ms 78828 KB Output is correct
15 Correct 398 ms 78580 KB Output is correct
16 Correct 404 ms 78592 KB Output is correct
17 Correct 200 ms 78668 KB Output is correct
18 Correct 91 ms 78668 KB Output is correct

Subtask #2
12.2222222222 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 245 ms 80792 KB Output is correct
2 Correct 419 ms 95804 KB Output is correct
3 Execution timed out 1083 ms 112040 KB Time limit exceeded
4 Correct 438 ms 79244 KB Output is correct
5 Execution timed out 1086 ms 95544 KB Time limit exceeded
6 Correct 559 ms 79228 KB Output is correct
7 Correct 249 ms 80840 KB Output is correct
8 Correct 342 ms 78716 KB Output is correct
9 Execution timed out 1083 ms 95572 KB Time limit exceeded
10 Execution timed out 1088 ms 112028 KB Time limit exceeded
11 Execution timed out 1075 ms 87140 KB Time limit exceeded
12 Correct 728 ms 79312 KB Output is correct
13 Correct 280 ms 79760 KB Output is correct
14 Correct 442 ms 79312 KB Output is correct
15 Execution timed out 1087 ms 87232 KB Time limit exceeded
16 Correct 442 ms 95764 KB Output is correct
17 Correct 918 ms 79240 KB Output is correct
18 Execution timed out 1075 ms 145104 KB Time limit exceeded

Subtask #3
31.4285714286 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1075 ms 87316 KB Time limit exceeded
2 Execution timed out 1076 ms 87384 KB Time limit exceeded
3 Execution timed out 1085 ms 87320 KB Time limit exceeded
4 Correct 839 ms 80256 KB Output is correct
5 Correct 469 ms 96272 KB Output is correct
6 Execution timed out 1038 ms 80796 KB Time limit exceeded
7 Execution timed out 1083 ms 95928 KB Time limit exceeded
8 Execution timed out 1076 ms 87492 KB Time limit exceeded
9 Execution timed out 1048 ms 87444 KB Time limit exceeded
10 Correct 834 ms 79816 KB Output is correct
11 Correct 641 ms 79472 KB Output is correct
12 Correct 979 ms 79820 KB Output is correct
13 Execution timed out 1078 ms 87188 KB Time limit exceeded
14 Correct 487 ms 79776 KB Output is correct
15 Correct 997 ms 79776 KB Output is correct
16 Execution timed out 1062 ms 79948 KB Time limit exceeded
17 Execution timed out 1083 ms 87252 KB Time limit exceeded
18 Execution timed out 1082 ms 87340 KB Time limit exceeded
19 Correct 464 ms 82884 KB Output is correct
20 Execution timed out 1088 ms 87320 KB Time limit exceeded
21 Correct 592 ms 80064 KB Output is correct
22 Execution timed out 1089 ms 95948 KB Time limit exceeded
23 Correct 449 ms 83144 KB Output is correct
24 Correct 217 ms 79824 KB Output is correct
25 Correct 790 ms 80060 KB Output is correct
26 Correct 812 ms 80256 KB Output is correct
27 Execution timed out 1088 ms 96024 KB Time limit exceeded
28 Correct 354 ms 80464 KB Output is correct
29 Execution timed out 1098 ms 96020 KB Time limit exceeded
30 Execution timed out 1086 ms 87488 KB Time limit exceeded
31 Correct 454 ms 80528 KB Output is correct
32 Correct 514 ms 80016 KB Output is correct
33 Correct 157 ms 79716 KB Output is correct
34 Execution timed out 1103 ms 95932 KB Time limit exceeded
35 Correct 403 ms 80312 KB Output is correct
36 Execution timed out 1074 ms 96012 KB Time limit exceeded
37 Correct 480 ms 96164 KB Output is correct
38 Execution timed out 1029 ms 80692 KB Time limit exceeded
39 Correct 292 ms 80000 KB Output is correct
40 Correct 994 ms 81112 KB Output is correct
41 Execution timed out 1084 ms 145388 KB Time limit exceeded
42 Correct 972 ms 80264 KB Output is correct