oj.uz

답안 #26494

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
26494 2017-07-01T12:57:30 Z samir_droubi Brunhilda’s Birthday (BOI13_brunhilda) C++14
23.6508 / 100
 1000 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
int n,q;
const int MX=(1e7);
const int mxn=(1e5)+5;

int dp[MX];
int a[mxn];
int mx=0;
int get(int up,int pr)
{
	if(up%pr==0)return -1;
	int dif=up-pr;
	int ans=pr+pr*(dif/pr);
	return ans;
}
int calc(int x)
{
	if(x<mx)return 1;
	if(dp[x]!=-1)return dp[x];
	int ans=(1e9);
	for(int i=0;i<n;++i)
	{
		int num=get(x,a[i]);
		if(num==-1)continue;
		ans=min(ans,1+calc(num));
	}
	return dp[x]=ans;
}
int main()
{
	memset(dp,-1,sizeof dp);
	scanf("%d%d",&n,&q);
	for(int i=0;i<n;++i)
	{
		scanf("%d",&a[i]);
		mx=max(mx,a[i]);
	}
	for(int i=0;i<q;++i)
	{
		int x;
		scanf("%d",&x);
		int ans=calc(x);
		if(ans==(1e9))printf("oo\n");
		else printf("%d\n",ans);
	}
	return 0;
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:33:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&q);
                     ^
brunhilda.cpp:36:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
                    ^
brunhilda.cpp:42:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
                 ^

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 41472 KB Output is correct
2 Correct 0 ms 41472 KB Output is correct
3 Correct 0 ms 41472 KB Output is correct
4 Correct 16 ms 41472 KB Output is correct
5 Correct 0 ms 41472 KB Output is correct
6 Correct 3 ms 41472 KB Output is correct
7 Correct 0 ms 41472 KB Output is correct
8 Correct 3 ms 41472 KB Output is correct
9 Correct 0 ms 41472 KB Output is correct
10 Correct 6 ms 41472 KB Output is correct
11 Correct 13 ms 41500 KB Output is correct
12 Correct 0 ms 41472 KB Output is correct
13 Correct 16 ms 41472 KB Output is correct
14 Correct 9 ms 41472 KB Output is correct
15 Correct 3 ms 41472 KB Output is correct
16 Correct 6 ms 41472 KB Output is correct
17 Correct 16 ms 41472 KB Output is correct
18 Correct 3 ms 41472 KB Output is correct

Subtask #2
2.22222222222 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1000 ms 45044 KB Execution timed out
2 Correct 33 ms 41472 KB Output is correct
3 Execution timed out 1000 ms 99664 KB Execution timed out
4 Execution timed out 1000 ms 72804 KB Execution timed out
5 Execution timed out 1000 ms 59952 KB Execution timed out
6 Execution timed out 1000 ms 52828 KB Execution timed out
7 Execution timed out 1000 ms 45044 KB Execution timed out
8 Execution timed out 1000 ms 53576 KB Execution timed out
9 Execution timed out 1000 ms 55000 KB Execution timed out
10 Execution timed out 1000 ms 99664 KB Execution timed out
11 Memory limit exceeded 76 ms 262144 KB Memory limit exceeded
12 Execution timed out 1000 ms 116168 KB Execution timed out
13 Execution timed out 1000 ms 73076 KB Execution timed out
14 Execution timed out 1000 ms 72808 KB Execution timed out
15 Execution timed out 1000 ms 89596 KB Execution timed out
16 Correct 13 ms 41472 KB Output is correct
17 Memory limit exceeded 139 ms 262144 KB Memory limit exceeded
18 Incorrect 13 ms 41472 KB Output isn't correct

Subtask #3
1.42857142857 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1000 ms 254268 KB Execution timed out
2 Execution timed out 1000 ms 244932 KB Execution timed out
3 Execution timed out 1000 ms 199248 KB Execution timed out
4 Execution timed out 1000 ms 148848 KB Execution timed out
5 Execution timed out 1000 ms 41680 KB Execution timed out
6 Execution timed out 1000 ms 207168 KB Execution timed out
7 Execution timed out 1000 ms 62144 KB Execution timed out
8 Execution timed out 1000 ms 254260 KB Execution timed out
9 Execution timed out 1000 ms 254264 KB Execution timed out
10 Execution timed out 1000 ms 48320 KB Execution timed out
11 Execution timed out 1000 ms 85392 KB Execution timed out
12 Execution timed out 1000 ms 168804 KB Execution timed out
13 Execution timed out 1000 ms 114788 KB Execution timed out
14 Execution timed out 1000 ms 196656 KB Execution timed out
15 Memory limit exceeded 86 ms 262144 KB Memory limit exceeded
16 Execution timed out 1000 ms 186480 KB Execution timed out
17 Execution timed out 1000 ms 51244 KB Execution timed out
18 Execution timed out 1000 ms 244932 KB Execution timed out
19 Execution timed out 1000 ms 53328 KB Execution timed out
20 Execution timed out 1000 ms 199248 KB Execution timed out
21 Memory limit exceeded 99 ms 262144 KB Memory limit exceeded
22 Execution timed out 1000 ms 188196 KB Execution timed out
23 Execution timed out 1000 ms 42156 KB Execution timed out
24 Execution timed out 1000 ms 49920 KB Execution timed out
25 Execution timed out 1000 ms 46936 KB Execution timed out
26 Execution timed out 1000 ms 148852 KB Execution timed out
27 Execution timed out 1000 ms 181696 KB Execution timed out
28 Execution timed out 1000 ms 88576 KB Execution timed out
29 Execution timed out 1000 ms 85900 KB Execution timed out
30 Execution timed out 1000 ms 67024 KB Execution timed out
31 Execution timed out 1000 ms 74920 KB Execution timed out
32 Execution timed out 1000 ms 78952 KB Execution timed out
33 Execution timed out 1000 ms 50100 KB Execution timed out
34 Execution timed out 1000 ms 62148 KB Execution timed out
35 Execution timed out 1000 ms 56372 KB Execution timed out
36 Execution timed out 1000 ms 203356 KB Execution timed out
37 Execution timed out 1000 ms 41680 KB Execution timed out
38 Execution timed out 1000 ms 207172 KB Execution timed out
39 Execution timed out 1000 ms 49592 KB Execution timed out
40 Execution timed out 1000 ms 100912 KB Execution timed out
41 Correct 36 ms 41472 KB Output is correct
42 Memory limit exceeded 99 ms 262144 KB Memory limit exceeded