oj.uz

Submission #31867

# Submission time Handle Problem Language Result Execution time Memory
31867 2017-09-11T08:12:59 Z huynd2001 Brunhilda’s Birthday (BOI13_brunhilda) C++14
8.88889 / 100
 453 ms 80532 KB 
/*huypheu
2 2
2 3
5
6
*/
#include <bits/stdc++.h>
#define oo (INT_MAX/2)
using namespace std;

int pri[10000005],dp[10000005];
int a[100005];

int main()
{
	int n,q;
	cin >> n >> q;
	for(int i=1;i<=n;i++)
	{
		cin >> a[i];
	}
	int maxo=10000007;
	for(int i=1;i<=maxo;i++) dp[i]=oo;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=(maxo/a[i]);j++)
		{
			pri[a[i]*j]=a[i];
		}
	}
	dp[0]=0;
	int curl=0,curr=0+pri[0]-1;
	for(int i=1;i<=maxo;i++)
	{
		while(i>curr)
		{
			curl++;
			curr=curl+pri[curl]-1;
		}
		if(curl==i) break;
		dp[i]=min(dp[curl]+1,dp[i]);
	}
	// for(int i=1;i<=10;i++)
	// {
	// 	cout << dp[i] << " ";	
	// }
	// cout << endl;
	for(int i=1;i<=q;i++)
	{
		int b;
		cin >> b;
		if(dp[b]>=maxo) cout << "oo\n"; else cout << dp[b] << "\n";
	}
	return 0;
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:23:35: warning: iteration 10000004u invokes undefined behavior [-Waggressive-loop-optimizations]
  for(int i=1;i<=maxo;i++) dp[i]=oo;
                                   ^
brunhilda.cpp:23:15: note: containing loop
  for(int i=1;i<=maxo;i++) dp[i]=oo;
               ^

Subtask #1
8.88888888889 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 80532 KB Output is correct
2 Runtime error 113 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Correct 39 ms 80532 KB Output is correct
4 Runtime error 73 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Correct 99 ms 80532 KB Output is correct
6 Correct 36 ms 80532 KB Output is correct
7 Correct 43 ms 80532 KB Output is correct
8 Correct 46 ms 80532 KB Output is correct
9 Correct 99 ms 80532 KB Output is correct
10 Correct 143 ms 80532 KB Output is correct
11 Runtime error 133 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 69 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 319 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 299 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 143 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 109 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 99 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 76 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 103 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 159 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 453 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 129 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 273 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 93 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 103 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 129 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 336 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 416 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 389 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 189 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 63 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 143 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 313 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 186 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 323 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 346 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 313 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 406 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 399 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 193 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 159 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 296 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 339 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 343 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 333 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 256 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 199 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 289 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 409 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 366 ms 80532 KB Execution timed out (wall clock limit exceeded)
15 Runtime error 306 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 366 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 333 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 369 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 79 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 386 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 216 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 423 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 149 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 73 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 216 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 183 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 443 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 93 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 399 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 373 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 116 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 156 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 69 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 299 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 86 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 423 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 169 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 296 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 109 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 259 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 273 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Runtime error 346 ms 80532 KB Execution killed with signal 11 (could be triggered by violating memory limits)