oj.uz

Submission #559574

# Submission time Handle Problem Language Result Execution time Memory
559574 2022-05-10T08:22:45 Z Trunkty Brunhilda’s Birthday (BOI13_brunhilda) C++14
100 / 100
 315 ms 119376 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

#define DEBUG
#ifdef DEBUG
  #define debug(x) cout << #x << ": " << x << endl
#else
  #define debug(x)
#endif

int m,q,mini=2e9;
int maxi[10000005];
int low[10000005];
int dp[10000005];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> m >> q;
	for(int i=1;i<=m;i++){
		int a;
		cin >> a;
		for(int j=a;j<=1e7;j+=a){
			maxi[j] = max(maxi[j],a);
		}
		mini = min(mini,10000000-10000000%a);
	}
	for(int i=1e7;i>=1;i--){
		low[i] = mini;
		mini = min(mini,i-maxi[i]);
	}
	for(int i=1;i<=1e7;i++){
		dp[i] = 2e9;
		dp[i] = dp[low[i]]+1;
	}
	for(int i=1;i<=q;i++){
		int a;
		cin >> a;
		if(dp[a]<2e9){
			cout << dp[a] << "\n";
		}
		else{
			cout << "oo" << "\n";
		}
	}
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 117612 KB Output is correct
2 Correct 96 ms 117660 KB Output is correct
3 Correct 102 ms 117644 KB Output is correct
4 Correct 92 ms 117764 KB Output is correct
5 Correct 102 ms 117644 KB Output is correct
6 Correct 81 ms 117704 KB Output is correct
7 Correct 85 ms 117796 KB Output is correct
8 Correct 90 ms 117680 KB Output is correct
9 Correct 112 ms 117652 KB Output is correct
10 Correct 143 ms 117616 KB Output is correct
11 Correct 110 ms 117660 KB Output is correct
12 Correct 78 ms 117708 KB Output is correct
13 Correct 187 ms 117708 KB Output is correct
14 Correct 198 ms 117884 KB Output is correct
15 Correct 106 ms 117696 KB Output is correct
16 Correct 96 ms 117644 KB Output is correct
17 Correct 102 ms 117708 KB Output is correct
18 Correct 76 ms 117708 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 117712 KB Output is correct
2 Correct 110 ms 118332 KB Output is correct
3 Correct 242 ms 118152 KB Output is correct
4 Correct 118 ms 117632 KB Output is correct
5 Correct 176 ms 117960 KB Output is correct
6 Correct 102 ms 117664 KB Output is correct
7 Correct 98 ms 117716 KB Output is correct
8 Correct 103 ms 117720 KB Output is correct
9 Correct 197 ms 118196 KB Output is correct
10 Correct 241 ms 118092 KB Output is correct
11 Correct 219 ms 117964 KB Output is correct
12 Correct 139 ms 117668 KB Output is correct
13 Correct 87 ms 117832 KB Output is correct
14 Correct 110 ms 117676 KB Output is correct
15 Correct 185 ms 117960 KB Output is correct
16 Correct 106 ms 118332 KB Output is correct
17 Correct 224 ms 117680 KB Output is correct
18 Correct 193 ms 118396 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 118376 KB Output is correct
2 Correct 255 ms 118300 KB Output is correct
3 Correct 285 ms 118596 KB Output is correct
4 Correct 158 ms 118584 KB Output is correct
5 Correct 133 ms 119360 KB Output is correct
6 Correct 216 ms 118720 KB Output is correct
7 Correct 185 ms 118932 KB Output is correct
8 Correct 198 ms 118416 KB Output is correct
9 Correct 213 ms 118632 KB Output is correct
10 Correct 160 ms 117776 KB Output is correct
11 Correct 137 ms 117964 KB Output is correct
12 Correct 190 ms 117968 KB Output is correct
13 Correct 243 ms 118872 KB Output is correct
14 Correct 141 ms 119040 KB Output is correct
15 Correct 194 ms 117964 KB Output is correct
16 Correct 233 ms 117968 KB Output is correct
17 Correct 182 ms 118020 KB Output is correct
18 Correct 264 ms 118216 KB Output is correct
19 Correct 98 ms 117968 KB Output is correct
20 Correct 241 ms 118600 KB Output is correct
21 Correct 181 ms 118984 KB Output is correct
22 Correct 287 ms 119372 KB Output is correct
23 Correct 125 ms 118940 KB Output is correct
24 Correct 123 ms 118724 KB Output is correct
25 Correct 198 ms 118792 KB Output is correct
26 Correct 154 ms 118552 KB Output is correct
27 Correct 315 ms 118856 KB Output is correct
28 Correct 115 ms 118708 KB Output is correct
29 Correct 242 ms 119376 KB Output is correct
30 Correct 233 ms 119092 KB Output is correct
31 Correct 128 ms 118600 KB Output is correct
32 Correct 149 ms 118644 KB Output is correct
33 Correct 97 ms 118660 KB Output is correct
34 Correct 180 ms 118988 KB Output is correct
35 Correct 131 ms 118724 KB Output is correct
36 Correct 245 ms 119308 KB Output is correct
37 Correct 149 ms 119356 KB Output is correct
38 Correct 219 ms 118664 KB Output is correct
39 Correct 113 ms 118768 KB Output is correct
40 Correct 182 ms 118828 KB Output is correct
41 Correct 210 ms 118920 KB Output is correct
42 Correct 217 ms 118900 KB Output is correct