oj.uz

답안 #26491

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
26491 2017-07-01T12:47:59 Z samir_droubi Brunhilda’s Birthday (BOI13_brunhilda) C++14
8.09524 / 100
 1000 ms 11520 KB 
#include <bits/stdc++.h>
using namespace std;
int n,q;
map<int,int>dp;
const int mxn=(1e5)+5;
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+dif/pr;
	return ans;
}
int calc(int x)
{
	if(x<mx)return 1;
	if(dp.count(x))return dp[x];
	int ans=(1e9);
	for(int i=0;i<n;++i)
	{
		int num=get(x,a[i]);
		if(num==-1)continue;
		ans=1+min(ans,calc(num));
	}
	return dp[x]=ans;
}
int main()
{
	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:30: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:33:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
                    ^
brunhilda.cpp:39:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
                 ^

Subtask #1
1.11111111111 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 2544 KB Output isn't correct
2 Incorrect 0 ms 2544 KB Output isn't correct
3 Incorrect 0 ms 2412 KB Output isn't correct
4 Incorrect 3 ms 2676 KB Output isn't correct
5 Incorrect 0 ms 2412 KB Output isn't correct
6 Incorrect 0 ms 2544 KB Output isn't correct
7 Incorrect 0 ms 2412 KB Output isn't correct
8 Incorrect 0 ms 2412 KB Output isn't correct
9 Incorrect 0 ms 2412 KB Output isn't correct
10 Incorrect 3 ms 2544 KB Output isn't correct
11 Incorrect 0 ms 2544 KB Output isn't correct
12 Correct 0 ms 2412 KB Output is correct
13 Incorrect 0 ms 2412 KB Output isn't correct
14 Incorrect 3 ms 2412 KB Output isn't correct
15 Incorrect 0 ms 2412 KB Output isn't correct
16 Incorrect 0 ms 2544 KB Output isn't correct
17 Incorrect 9 ms 2808 KB Output isn't correct
18 Incorrect 9 ms 2676 KB Output isn't correct

Subtask #2
5.55555555556 / 20.0

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

Subtask #3
1.42857142857 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1000 ms 2544 KB Execution timed out
2 Execution timed out 1000 ms 2544 KB Execution timed out
3 Execution timed out 1000 ms 2544 KB Execution timed out
4 Execution timed out 1000 ms 4656 KB Execution timed out
5 Execution timed out 1000 ms 2544 KB Execution timed out
6 Execution timed out 1000 ms 3468 KB Execution timed out
7 Execution timed out 1000 ms 2544 KB Execution timed out
8 Execution timed out 1000 ms 2544 KB Execution timed out
9 Execution timed out 1000 ms 2544 KB Execution timed out
10 Execution timed out 1000 ms 3732 KB Execution timed out
11 Execution timed out 1000 ms 4128 KB Execution timed out
12 Execution timed out 1000 ms 3732 KB Execution timed out
13 Execution timed out 1000 ms 2676 KB Execution timed out
14 Execution timed out 1000 ms 11520 KB Execution timed out
15 Execution timed out 1000 ms 3864 KB Execution timed out
16 Execution timed out 1000 ms 3600 KB Execution timed out
17 Execution timed out 1000 ms 2544 KB Execution timed out
18 Execution timed out 1000 ms 2544 KB Execution timed out
19 Execution timed out 1000 ms 3864 KB Execution timed out
20 Execution timed out 1000 ms 2544 KB Execution timed out
21 Execution timed out 1000 ms 7032 KB Execution timed out
22 Execution timed out 1000 ms 2544 KB Execution timed out
23 Execution timed out 1000 ms 2676 KB Execution timed out
24 Execution timed out 1000 ms 8352 KB Execution timed out
25 Execution timed out 1000 ms 4920 KB Execution timed out
26 Execution timed out 1000 ms 4656 KB Execution timed out
27 Execution timed out 1000 ms 2544 KB Execution timed out
28 Execution timed out 1000 ms 8748 KB Execution timed out
29 Execution timed out 1000 ms 2544 KB Execution timed out
30 Execution timed out 1000 ms 2544 KB Execution timed out
31 Execution timed out 1000 ms 4128 KB Execution timed out
32 Execution timed out 1000 ms 5052 KB Execution timed out
33 Execution timed out 1000 ms 8220 KB Execution timed out
34 Execution timed out 1000 ms 2544 KB Execution timed out
35 Execution timed out 1000 ms 6108 KB Execution timed out
36 Execution timed out 1000 ms 2544 KB Execution timed out
37 Execution timed out 1000 ms 2544 KB Execution timed out
38 Execution timed out 1000 ms 3336 KB Execution timed out
39 Execution timed out 1000 ms 5844 KB Execution timed out
40 Execution timed out 1000 ms 3336 KB Execution timed out
41 Correct 46 ms 2412 KB Output is correct
42 Execution timed out 1000 ms 4920 KB Execution timed out