답안 #971678

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
971678	2024-04-29T07:44:16 Z	NintsiChkhaidze	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	77.4603 / 100	377 ms	80992 KB

brunhilda

#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 = 10000000;
	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

#	결과	실행 시간	메모리	Grader output
1	Correct	88 ms	78680 KB	Output is correct
2	Correct	98 ms	78736 KB	Output is correct
3	Correct	84 ms	78684 KB	Output is correct
4	Correct	86 ms	78684 KB	Output is correct
5	Correct	88 ms	78544 KB	Output is correct
6	Correct	76 ms	78672 KB	Output is correct
7	Correct	82 ms	78676 KB	Output is correct
8	Correct	88 ms	78732 KB	Output is correct
9	Correct	98 ms	78676 KB	Output is correct
10	Correct	115 ms	78736 KB	Output is correct
11	Correct	110 ms	78740 KB	Output is correct
12	Correct	73 ms	78684 KB	Output is correct
13	Correct	197 ms	78748 KB	Output is correct
14	Correct	195 ms	78680 KB	Output is correct
15	Correct	101 ms	78680 KB	Output is correct
16	Correct	97 ms	78684 KB	Output is correct
17	Correct	109 ms	78748 KB	Output is correct
18	Correct	87 ms	78684 KB	Output is correct

Subtask #2

18.8888888889 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	87 ms	78868 KB	Output is correct
2	Correct	105 ms	79952 KB	Output is correct
3	Correct	252 ms	79484 KB	Output is correct
4	Correct	110 ms	78740 KB	Output is correct
5	Correct	170 ms	79184 KB	Output is correct
6	Correct	94 ms	78908 KB	Output is correct
7	Correct	87 ms	78680 KB	Output is correct
8	Correct	110 ms	78680 KB	Output is correct
9	Correct	198 ms	79260 KB	Output is correct
10	Correct	240 ms	79440 KB	Output is correct
11	Incorrect	238 ms	79120 KB	Output isn't correct
12	Correct	135 ms	78956 KB	Output is correct
13	Correct	80 ms	78680 KB	Output is correct
14	Correct	109 ms	78764 KB	Output is correct
15	Correct	198 ms	79272 KB	Output is correct
16	Correct	107 ms	79700 KB	Output is correct
17	Correct	205 ms	78768 KB	Output is correct
18	Correct	195 ms	79696 KB	Output is correct

Subtask #3

38.5714285714 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	238 ms	79444 KB	Output is correct
2	Correct	283 ms	79432 KB	Output is correct
3	Correct	303 ms	79780 KB	Output is correct
4	Incorrect	250 ms	79700 KB	Output isn't correct
5	Incorrect	234 ms	80724 KB	Output isn't correct
6	Correct	305 ms	79772 KB	Output is correct
7	Correct	244 ms	80260 KB	Output is correct
8	Correct	258 ms	79512 KB	Output is correct
9	Correct	249 ms	79440 KB	Output is correct
10	Correct	170 ms	78684 KB	Output is correct
11	Incorrect	167 ms	79004 KB	Output isn't correct
12	Correct	202 ms	78932 KB	Output is correct
13	Correct	328 ms	79956 KB	Output is correct
14	Correct	238 ms	80028 KB	Output is correct
15	Incorrect	228 ms	79000 KB	Output isn't correct
16	Correct	240 ms	79136 KB	Output is correct
17	Correct	205 ms	79260 KB	Output is correct
18	Correct	274 ms	79444 KB	Output is correct
19	Incorrect	114 ms	79368 KB	Output isn't correct
20	Correct	304 ms	79700 KB	Output is correct
21	Incorrect	265 ms	80028 KB	Output isn't correct
22	Correct	377 ms	80708 KB	Output is correct
23	Correct	227 ms	80004 KB	Output is correct
24	Correct	211 ms	79700 KB	Output is correct
25	Incorrect	278 ms	79700 KB	Output isn't correct
26	Incorrect	252 ms	79952 KB	Output isn't correct
27	Correct	318 ms	80284 KB	Output is correct
28	Incorrect	208 ms	79604 KB	Output isn't correct
29	Correct	350 ms	80992 KB	Output is correct
30	Correct	355 ms	80480 KB	Output is correct
31	Correct	211 ms	79448 KB	Output is correct
32	Incorrect	232 ms	79696 KB	Output isn't correct
33	Incorrect	190 ms	79444 KB	Output isn't correct
34	Correct	243 ms	80520 KB	Output is correct
35	Incorrect	215 ms	79788 KB	Output isn't correct
36	Correct	370 ms	80608 KB	Output is correct
37	Incorrect	230 ms	80688 KB	Output isn't correct
38	Correct	312 ms	79760 KB	Output is correct
39	Incorrect	219 ms	79696 KB	Output isn't correct
40	Correct	270 ms	79964 KB	Output is correct
41	Correct	226 ms	80212 KB	Output is correct
42	Incorrect	324 ms	79952 KB	Output isn't correct