답안 #378492

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
378492	2021-03-17T00:49:54 Z	YJU	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	97.7778 / 100	441 ms	190060 KB

brunhilda

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll N=12e6+5;
const ll INF=1e9+1;
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define X first
#define Y second
#define pb push_back
#define mp make_pair
#define lwb lower_bound

ll m,q,x,jump[N],dp[N];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>m>>q;
	REP(i,m){
		cin>>x;
		for(int j=x-1;j<N;j+=x){
			jump[j]=x-1;
		}
	}
	for(int i=N-1;i>=1;i--){
		jump[i]=max(jump[i],jump[i+1]-1);
	}
	for(int i=1;i<N;i++){
		dp[i]=(i>=jump[i]&&jump[i]!=0?min(INF,dp[i-jump[i]]+1):INF);
	}
	while(q--){
		cin>>x;
		if(dp[x]==INF){
			cout<<"OO\n";
		}else{
			cout<<dp[x]<<"\n";
		}
	}
	return 0;
}

Subtask #1

17.7777777778 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	144 ms	188268 KB	Output isn't correct
2	Correct	175 ms	188268 KB	Output is correct
3	Correct	161 ms	188140 KB	Output is correct
4	Correct	142 ms	188268 KB	Output is correct
5	Correct	160 ms	188140 KB	Output is correct
6	Incorrect	147 ms	188268 KB	Output isn't correct
7	Correct	159 ms	188140 KB	Output is correct
8	Correct	174 ms	188268 KB	Output is correct
9	Correct	194 ms	188268 KB	Output is correct
10	Correct	219 ms	188236 KB	Output is correct
11	Correct	208 ms	188268 KB	Output is correct
12	Correct	138 ms	188140 KB	Output is correct
13	Correct	331 ms	188268 KB	Output is correct
14	Correct	331 ms	188292 KB	Output is correct
15	Correct	185 ms	188140 KB	Output is correct
16	Correct	181 ms	188140 KB	Output is correct
17	Correct	167 ms	188300 KB	Output is correct
18	Correct	146 ms	188268 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	163 ms	188268 KB	Output is correct
2	Correct	184 ms	188908 KB	Output is correct
3	Correct	401 ms	188652 KB	Output is correct
4	Correct	193 ms	188268 KB	Output is correct
5	Correct	293 ms	188524 KB	Output is correct
6	Correct	167 ms	188268 KB	Output is correct
7	Correct	161 ms	188268 KB	Output is correct
8	Correct	184 ms	188268 KB	Output is correct
9	Correct	323 ms	188780 KB	Output is correct
10	Correct	397 ms	188624 KB	Output is correct
11	Correct	382 ms	188524 KB	Output is correct
12	Correct	238 ms	188268 KB	Output is correct
13	Correct	155 ms	188304 KB	Output is correct
14	Correct	185 ms	188268 KB	Output is correct
15	Correct	331 ms	188524 KB	Output is correct
16	Correct	180 ms	189036 KB	Output is correct
17	Correct	342 ms	188268 KB	Output is correct
18	Correct	331 ms	189036 KB	Output is correct

Subtask #3

60.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	350 ms	188908 KB	Output is correct
2	Correct	409 ms	189036 KB	Output is correct
3	Correct	414 ms	189164 KB	Output is correct
4	Correct	271 ms	189164 KB	Output is correct
5	Correct	218 ms	189932 KB	Output is correct
6	Correct	348 ms	189292 KB	Output is correct
7	Correct	296 ms	189548 KB	Output is correct
8	Correct	353 ms	189036 KB	Output is correct
9	Correct	350 ms	188908 KB	Output is correct
10	Correct	271 ms	188396 KB	Output is correct
11	Correct	236 ms	188524 KB	Output is correct
12	Correct	314 ms	188524 KB	Output is correct
13	Correct	384 ms	189548 KB	Output is correct
14	Correct	246 ms	189676 KB	Output is correct
15	Correct	333 ms	188396 KB	Output is correct
16	Correct	364 ms	188524 KB	Output is correct
17	Correct	320 ms	188652 KB	Output is correct
18	Correct	407 ms	188876 KB	Output is correct
19	Correct	163 ms	188464 KB	Output is correct
20	Correct	409 ms	189292 KB	Output is correct
21	Correct	284 ms	189584 KB	Output is correct
22	Correct	425 ms	190060 KB	Output is correct
23	Correct	222 ms	189420 KB	Output is correct
24	Correct	183 ms	189420 KB	Output is correct
25	Correct	286 ms	189292 KB	Output is correct
26	Correct	271 ms	189292 KB	Output is correct
27	Correct	441 ms	189420 KB	Output is correct
28	Correct	181 ms	189420 KB	Output is correct
29	Correct	389 ms	189932 KB	Output is correct
30	Correct	365 ms	189676 KB	Output is correct
31	Correct	207 ms	189292 KB	Output is correct
32	Correct	222 ms	189232 KB	Output is correct
33	Correct	170 ms	189420 KB	Output is correct
34	Correct	295 ms	189536 KB	Output is correct
35	Correct	189 ms	189420 KB	Output is correct
36	Correct	425 ms	189932 KB	Output is correct
37	Correct	219 ms	190060 KB	Output is correct
38	Correct	349 ms	189292 KB	Output is correct
39	Correct	194 ms	189292 KB	Output is correct
40	Correct	301 ms	189420 KB	Output is correct
41	Correct	270 ms	189536 KB	Output is correct
42	Correct	370 ms	189548 KB	Output is correct