답안 #378493

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
378493	2021-03-17T00:50:35 Z	YJU	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	97.7778 / 100	441 ms	189036 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]>x){
			cout<<"OO\n";
		}else{
			cout<<dp[x]<<"\n";
		}
	}
	return 0;
}

Subtask #1

17.7777777778 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	144 ms	188140 KB	Output isn't correct
2	Correct	169 ms	188140 KB	Output is correct
3	Correct	160 ms	188140 KB	Output is correct
4	Correct	142 ms	188268 KB	Output is correct
5	Correct	157 ms	188140 KB	Output is correct
6	Incorrect	143 ms	188140 KB	Output isn't correct
7	Correct	163 ms	188268 KB	Output is correct
8	Correct	170 ms	188268 KB	Output is correct
9	Correct	197 ms	188140 KB	Output is correct
10	Correct	230 ms	188140 KB	Output is correct
11	Correct	205 ms	188268 KB	Output is correct
12	Correct	140 ms	188140 KB	Output is correct
13	Correct	325 ms	188268 KB	Output is correct
14	Correct	328 ms	188236 KB	Output is correct
15	Correct	197 ms	188268 KB	Output is correct
16	Correct	171 ms	188140 KB	Output is correct
17	Correct	168 ms	188268 KB	Output is correct
18	Correct	142 ms	188184 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	165 ms	188140 KB	Output is correct
2	Correct	190 ms	188344 KB	Output is correct
3	Correct	397 ms	188268 KB	Output is correct
4	Correct	184 ms	188140 KB	Output is correct
5	Correct	284 ms	188252 KB	Output is correct
6	Correct	166 ms	188140 KB	Output is correct
7	Correct	161 ms	188140 KB	Output is correct
8	Correct	183 ms	188268 KB	Output is correct
9	Correct	321 ms	188140 KB	Output is correct
10	Correct	395 ms	188268 KB	Output is correct
11	Correct	385 ms	188140 KB	Output is correct
12	Correct	235 ms	188140 KB	Output is correct
13	Correct	152 ms	188140 KB	Output is correct
14	Correct	188 ms	188268 KB	Output is correct
15	Correct	329 ms	188348 KB	Output is correct
16	Correct	189 ms	188392 KB	Output is correct
17	Correct	337 ms	188140 KB	Output is correct
18	Correct	326 ms	188268 KB	Output is correct

Subtask #3

60.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	345 ms	188268 KB	Output is correct
2	Correct	405 ms	188268 KB	Output is correct
3	Correct	414 ms	188524 KB	Output is correct
4	Correct	270 ms	188524 KB	Output is correct
5	Correct	218 ms	188396 KB	Output is correct
6	Correct	346 ms	188524 KB	Output is correct
7	Correct	296 ms	188396 KB	Output is correct
8	Correct	345 ms	188268 KB	Output is correct
9	Correct	350 ms	188396 KB	Output is correct
10	Correct	275 ms	188268 KB	Output is correct
11	Correct	237 ms	188268 KB	Output is correct
12	Correct	313 ms	188292 KB	Output is correct
13	Correct	387 ms	188652 KB	Output is correct
14	Correct	248 ms	188780 KB	Output is correct
15	Correct	337 ms	188396 KB	Output is correct
16	Correct	360 ms	188380 KB	Output is correct
17	Correct	314 ms	188396 KB	Output is correct
18	Correct	409 ms	188224 KB	Output is correct
19	Correct	165 ms	188348 KB	Output is correct
20	Correct	404 ms	188652 KB	Output is correct
21	Correct	281 ms	189036 KB	Output is correct
22	Correct	424 ms	188524 KB	Output is correct
23	Correct	215 ms	188524 KB	Output is correct
24	Correct	192 ms	188524 KB	Output is correct
25	Correct	286 ms	188524 KB	Output is correct
26	Correct	270 ms	188524 KB	Output is correct
27	Correct	441 ms	188312 KB	Output is correct
28	Correct	184 ms	188652 KB	Output is correct
29	Correct	390 ms	188524 KB	Output is correct
30	Correct	360 ms	188396 KB	Output is correct
31	Correct	210 ms	188396 KB	Output is correct
32	Correct	222 ms	188652 KB	Output is correct
33	Correct	171 ms	188396 KB	Output is correct
34	Correct	296 ms	188396 KB	Output is correct
35	Correct	190 ms	188524 KB	Output is correct
36	Correct	415 ms	188480 KB	Output is correct
37	Correct	219 ms	188396 KB	Output is correct
38	Correct	343 ms	188432 KB	Output is correct
39	Correct	194 ms	188524 KB	Output is correct
40	Correct	306 ms	188464 KB	Output is correct
41	Correct	270 ms	188396 KB	Output is correct
42	Correct	372 ms	188780 KB	Output is correct