oj.uz

Submission #26493

# Submission time Handle Problem Language Result Execution time Memory
26493 2017-07-01T12:52: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;
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+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=min(ans,1+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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2544 KB Output is correct
2 Correct 16 ms 2676 KB Output is correct
3 Correct 0 ms 2548 KB Output is correct
4 Correct 19 ms 2676 KB Output is correct
5 Correct 0 ms 2412 KB Output is correct
6 Correct 0 ms 2544 KB Output is correct
7 Correct 0 ms 2544 KB Output is correct
8 Correct 0 ms 2676 KB Output is correct
9 Correct 0 ms 2412 KB Output is correct
10 Correct 6 ms 2752 KB Output is correct
11 Correct 9 ms 2936 KB Output is correct
12 Correct 0 ms 2412 KB Output is correct
13 Correct 33 ms 2412 KB Output is correct
14 Correct 0 ms 2412 KB Output is correct
15 Correct 13 ms 2676 KB Output is correct
16 Correct 16 ms 2676 KB Output is correct
17 Correct 56 ms 2808 KB Output is correct
18 Correct 19 ms 2676 KB Output is correct

Subtask #2
2.22222222222 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 8708 KB Execution timed out
2 Correct 13 ms 2412 KB Output is correct
3 Execution timed out 1000 ms 99608 KB Execution timed out
4 Execution timed out 1000 ms 55116 KB Execution timed out
5 Execution timed out 1000 ms 33432 KB Execution timed out
6 Execution timed out 1000 ms 22088 KB Execution timed out
7 Execution timed out 1000 ms 8712 KB Execution timed out
8 Execution timed out 1000 ms 23328 KB Execution timed out
9 Execution timed out 1000 ms 25172 KB Execution timed out
10 Execution timed out 1000 ms 99612 KB Execution timed out
11 Memory limit exceeded 86 ms 262144 KB Memory limit exceeded
12 Execution timed out 1000 ms 127508 KB Execution timed out
13 Execution timed out 1000 ms 55692 KB Execution timed out
14 Execution timed out 1000 ms 55120 KB Execution timed out
15 Execution timed out 1000 ms 82840 KB Execution timed out
16 Correct 13 ms 2412 KB Output is correct
17 Memory limit exceeded 76 ms 262144 KB Memory limit exceeded
18 Execution timed out 1000 ms 146908 KB Execution timed out

Subtask #3
1.42857142857 / 60.0

# Verdict Execution time Memory Grader output
1 Memory limit exceeded 129 ms 262144 KB Memory limit exceeded
2 Memory limit exceeded 73 ms 262144 KB Memory limit exceeded
3 Memory limit exceeded 89 ms 262144 KB Memory limit exceeded
4 Execution timed out 1000 ms 181856 KB Execution timed out
5 Execution timed out 1000 ms 2984 KB Execution timed out
6 Memory limit exceeded 86 ms 262144 KB Memory limit exceeded
7 Execution timed out 1000 ms 37080 KB Execution timed out
8 Memory limit exceeded 99 ms 262144 KB Memory limit exceeded
9 Memory limit exceeded 116 ms 262144 KB Memory limit exceeded
10 Execution timed out 1000 ms 14304 KB Execution timed out
11 Execution timed out 1000 ms 76088 KB Execution timed out
12 Execution timed out 1000 ms 215108 KB Execution timed out
13 Execution timed out 1000 ms 124820 KB Execution timed out
14 Memory limit exceeded 223 ms 262144 KB Memory limit exceeded
15 Memory limit exceeded 83 ms 262144 KB Memory limit exceeded
16 Execution timed out 1000 ms 244436 KB Execution timed out
17 Execution timed out 1000 ms 18912 KB Execution timed out
18 Memory limit exceeded 76 ms 262144 KB Memory limit exceeded
19 Execution timed out 1000 ms 22664 KB Execution timed out
20 Memory limit exceeded 86 ms 262144 KB Memory limit exceeded
21 Memory limit exceeded 76 ms 262144 KB Memory limit exceeded
22 Execution timed out 1000 ms 247168 KB Execution timed out
23 Execution timed out 1000 ms 3768 KB Execution timed out
24 Execution timed out 1000 ms 17236 KB Execution timed out
25 Execution timed out 1000 ms 11996 KB Execution timed out
26 Execution timed out 1000 ms 181856 KB Execution timed out
27 Execution timed out 1000 ms 236336 KB Execution timed out
28 Execution timed out 1000 ms 81660 KB Execution timed out
29 Execution timed out 1000 ms 76668 KB Execution timed out
30 Execution timed out 1000 ms 45220 KB Execution timed out
31 Execution timed out 1000 ms 58628 KB Execution timed out
32 Execution timed out 1000 ms 65356 KB Execution timed out
33 Execution timed out 1000 ms 17408 KB Execution timed out
34 Execution timed out 1000 ms 37080 KB Execution timed out
35 Execution timed out 1000 ms 27852 KB Execution timed out
36 Memory limit exceeded 89 ms 262144 KB Memory limit exceeded
37 Execution timed out 1000 ms 2984 KB Execution timed out
38 Memory limit exceeded 96 ms 262144 KB Memory limit exceeded
39 Execution timed out 1000 ms 16416 KB Execution timed out
40 Execution timed out 1000 ms 101832 KB Execution timed out
41 Correct 26 ms 2412 KB Output is correct
42 Memory limit exceeded 86 ms 262144 KB Memory limit exceeded