oj.uz

Submission #971679

# Submission time Handle Problem Language Result Execution time Memory
971679 2024-04-29T07:45:28 Z NintsiChkhaidze Brunhilda’s Birthday (BOI13_brunhilda) C++17
100 / 100
 670 ms 158604 KB 
#include <bits/stdc++.h>
#define s second
#define f first
#define pb push_back
#define pii pair <int,int>
using namespace std;
 
const int N = 1e6 + 5;
int a[100003],inf=1e9;

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
 
	int n,q;
	cin>>n>>q;
 
	int m = 20000000;
	vector <int> prv(m + 1),dp(m + 1);
	for (int i = 1;i <= n; i++){
		cin >> a[i];
		for (int j = a[i] - 1; j <= m; j += a[i])
			prv[j] = max(prv[j],a[i] - 1);
	}
	
	for (int i=m;i>=1;i--){
		prv[i]=max(prv[i],prv[i + 1] - 1);
	}

	dp[0] = 0;
	for (int i = 1;i <= m; i++){
		dp[i] = inf;
		if (i >= prv[i]) 
			dp[i] = min(dp[i],dp[i - prv[i]] + 1);
	}
 	
	while (q--){
		int x;
		cin>>x;
		if (dp[x] == 1e9) cout<<"oo"<<endl;
		else cout<<dp[x]<<endl;
	}
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 157012 KB Output is correct
2 Correct 199 ms 157012 KB Output is correct
3 Correct 169 ms 157008 KB Output is correct
4 Correct 168 ms 157016 KB Output is correct
5 Correct 181 ms 157012 KB Output is correct
6 Correct 155 ms 157008 KB Output is correct
7 Correct 175 ms 157008 KB Output is correct
8 Correct 179 ms 157008 KB Output is correct
9 Correct 202 ms 156972 KB Output is correct
10 Correct 236 ms 157016 KB Output is correct
11 Correct 223 ms 157012 KB Output is correct
12 Correct 152 ms 157008 KB Output is correct
13 Correct 397 ms 157016 KB Output is correct
14 Correct 411 ms 157012 KB Output is correct
15 Correct 210 ms 157012 KB Output is correct
16 Correct 205 ms 157012 KB Output is correct
17 Correct 236 ms 156836 KB Output is correct
18 Correct 211 ms 157028 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 157152 KB Output is correct
2 Correct 230 ms 157800 KB Output is correct
3 Correct 547 ms 157756 KB Output is correct
4 Correct 237 ms 157044 KB Output is correct
5 Correct 382 ms 157644 KB Output is correct
6 Correct 203 ms 156836 KB Output is correct
7 Correct 186 ms 157140 KB Output is correct
8 Correct 221 ms 157020 KB Output is correct
9 Correct 431 ms 157544 KB Output is correct
10 Correct 494 ms 157756 KB Output is correct
11 Correct 520 ms 157668 KB Output is correct
12 Correct 283 ms 157024 KB Output is correct
13 Correct 184 ms 157212 KB Output is correct
14 Correct 248 ms 157048 KB Output is correct
15 Correct 431 ms 157456 KB Output is correct
16 Correct 211 ms 157796 KB Output is correct
17 Correct 419 ms 157012 KB Output is correct
18 Correct 423 ms 157800 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 157864 KB Output is correct
2 Correct 545 ms 157688 KB Output is correct
3 Correct 605 ms 157872 KB Output is correct
4 Correct 419 ms 157732 KB Output is correct
5 Correct 367 ms 158488 KB Output is correct
6 Correct 531 ms 157792 KB Output is correct
7 Correct 485 ms 158256 KB Output is correct
8 Correct 491 ms 157804 KB Output is correct
9 Correct 500 ms 157764 KB Output is correct
10 Correct 382 ms 157200 KB Output is correct
11 Correct 350 ms 157284 KB Output is correct
12 Correct 436 ms 157284 KB Output is correct
13 Correct 587 ms 158060 KB Output is correct
14 Correct 390 ms 158108 KB Output is correct
15 Correct 418 ms 157332 KB Output is correct
16 Correct 478 ms 157300 KB Output is correct
17 Correct 434 ms 157840 KB Output is correct
18 Correct 561 ms 157544 KB Output is correct
19 Correct 214 ms 157288 KB Output is correct
20 Correct 617 ms 157848 KB Output is correct
21 Correct 438 ms 158316 KB Output is correct
22 Correct 649 ms 158412 KB Output is correct
23 Correct 373 ms 157968 KB Output is correct
24 Correct 310 ms 157664 KB Output is correct
25 Correct 466 ms 157840 KB Output is correct
26 Correct 426 ms 157700 KB Output is correct
27 Correct 637 ms 158308 KB Output is correct
28 Correct 319 ms 158036 KB Output is correct
29 Correct 670 ms 158400 KB Output is correct
30 Correct 604 ms 158604 KB Output is correct
31 Correct 326 ms 157540 KB Output is correct
32 Correct 360 ms 157904 KB Output is correct
33 Correct 305 ms 157544 KB Output is correct
34 Correct 448 ms 158044 KB Output is correct
35 Correct 339 ms 158288 KB Output is correct
36 Correct 610 ms 158376 KB Output is correct
37 Correct 378 ms 158544 KB Output is correct
38 Correct 517 ms 157776 KB Output is correct
39 Correct 343 ms 158200 KB Output is correct
40 Correct 450 ms 157636 KB Output is correct
41 Correct 410 ms 158044 KB Output is correct
42 Correct 570 ms 158032 KB Output is correct