답안 #31866

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
31866 2017-09-11T08:08:19 Z huynd2001 Brunhilda’s Birthday (BOI13_brunhilda) C++14
62.8571 / 100
656 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;
		}
		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:40:30: warning: iteration 10000004u invokes undefined behavior [-Waggressive-loop-optimizations]
   dp[i]=min(dp[curl]+1,dp[i]);
                              ^
brunhilda.cpp:33:15: note: containing loop
  for(int i=1;i<=maxo;i++)
               ^
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;
               ^
# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 80532 KB Output is correct
2 Correct 103 ms 80532 KB Output is correct
3 Correct 83 ms 80532 KB Output is correct
4 Correct 109 ms 80532 KB Output is correct
5 Correct 126 ms 80532 KB Output is correct
6 Correct 66 ms 80532 KB Output is correct
7 Correct 83 ms 80532 KB Output is correct
8 Correct 83 ms 80532 KB Output is correct
9 Correct 106 ms 80532 KB Output is correct
10 Correct 146 ms 80532 KB Output is correct
11 Correct 133 ms 80532 KB Output is correct
12 Correct 53 ms 80532 KB Output is correct
13 Correct 316 ms 80532 KB Output is correct
14 Correct 366 ms 80532 KB Output is correct
15 Correct 119 ms 80532 KB Output is correct
16 Correct 89 ms 80532 KB Output is correct
17 Correct 163 ms 80532 KB Output is correct
18 Correct 119 ms 80532 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 93 ms 80532 KB Output is correct
2 Correct 139 ms 80532 KB Output is correct
3 Correct 406 ms 80532 KB Output is correct
4 Correct 119 ms 80532 KB Output is correct
5 Correct 286 ms 80532 KB Output is correct
6 Correct 79 ms 80532 KB Output is correct
7 Correct 89 ms 80532 KB Output is correct
8 Correct 133 ms 80532 KB Output is correct
9 Correct 333 ms 80532 KB Output is correct
10 Correct 416 ms 80532 KB Output is correct
11 Correct 386 ms 80532 KB Output is correct
12 Correct 166 ms 80532 KB Output is correct
13 Correct 63 ms 80532 KB Output is correct
14 Correct 123 ms 80532 KB Output is correct
15 Correct 303 ms 80532 KB Output is correct
16 Correct 123 ms 80532 KB Output is correct
17 Correct 306 ms 80532 KB Output is correct
18 Correct 333 ms 80532 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 473 ms 80532 KB Output is correct
2 Runtime error 649 ms 80532 KB Execution timed out (wall clock limit exceeded)
3 Runtime error 609 ms 80532 KB Execution timed out (wall clock limit exceeded)
4 Runtime error 403 ms 80532 KB Execution timed out (wall clock limit exceeded)
5 Runtime error 353 ms 80532 KB Execution timed out (wall clock limit exceeded)
6 Runtime error 546 ms 80532 KB Execution timed out (wall clock limit exceeded)
7 Runtime error 436 ms 80532 KB Execution timed out (wall clock limit exceeded)
8 Correct 489 ms 80532 KB Output is correct
9 Correct 416 ms 80532 KB Output is correct
10 Correct 276 ms 80532 KB Output is correct
11 Correct 313 ms 80532 KB Output is correct
12 Correct 363 ms 80532 KB Output is correct
13 Runtime error 553 ms 80532 KB Execution timed out (wall clock limit exceeded)
14 Runtime error 336 ms 80532 KB Execution timed out (wall clock limit exceeded)
15 Correct 413 ms 80532 KB Output is correct
16 Correct 556 ms 80532 KB Output is correct
17 Correct 319 ms 80532 KB Output is correct
18 Correct 459 ms 80532 KB Output is correct
19 Correct 149 ms 80532 KB Output is correct
20 Runtime error 636 ms 80532 KB Execution timed out (wall clock limit exceeded)
21 Runtime error 379 ms 80532 KB Execution timed out (wall clock limit exceeded)
22 Runtime error 593 ms 80532 KB Execution timed out (wall clock limit exceeded)
23 Runtime error 319 ms 80532 KB Execution timed out (wall clock limit exceeded)
24 Runtime error 246 ms 80532 KB Execution timed out (wall clock limit exceeded)
25 Runtime error 363 ms 80532 KB Execution timed out (wall clock limit exceeded)
26 Runtime error 373 ms 80532 KB Execution timed out (wall clock limit exceeded)
27 Correct 579 ms 80532 KB Output is correct
28 Runtime error 193 ms 80532 KB Execution timed out (wall clock limit exceeded)
29 Runtime error 656 ms 80532 KB Execution timed out (wall clock limit exceeded)
30 Runtime error 526 ms 80532 KB Execution timed out (wall clock limit exceeded)
31 Runtime error 263 ms 80532 KB Execution timed out (wall clock limit exceeded)
32 Runtime error 363 ms 80532 KB Execution timed out (wall clock limit exceeded)
33 Runtime error 276 ms 80532 KB Execution timed out (wall clock limit exceeded)
34 Correct 373 ms 80532 KB Output is correct
35 Runtime error 249 ms 80532 KB Execution timed out (wall clock limit exceeded)
36 Runtime error 603 ms 80532 KB Execution timed out (wall clock limit exceeded)
37 Correct 313 ms 80532 KB Output is correct
38 Correct 496 ms 80532 KB Output is correct
39 Runtime error 246 ms 80532 KB Execution timed out (wall clock limit exceeded)
40 Runtime error 369 ms 80532 KB Execution timed out (wall clock limit exceeded)
41 Runtime error 423 ms 80532 KB Execution timed out (wall clock limit exceeded)
42 Correct 603 ms 80532 KB Output is correct