oj.uz

Submission #239420

# Submission time Handle Problem Language Result Execution time Memory
239420 2020-06-15T14:25:39 Z luciocf Brunhilda’s Birthday (BOI13_brunhilda) C++14
0 / 100
 334 ms 42232 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;
const int maxv = 1e7+10;

int p[maxn];

int dp[maxv];

int main(void)
{
	int n, q;
	scanf("%d %d", &n, &q);

	int prod = 1;

	for (int i = 0; i < maxv; i++)
		dp[i] = 2*maxv;

	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &p[i]);
			
		if (prod != maxv)
		{
			if (1ll*prod*p[i] > 1ll*maxv)
				prod = maxv;
			else
				prod *= p[i];
		}

		for (int j = 0; j < maxv; j += p[i])
		{
			int a = min(maxv-1, j+p[i]-1);

			dp[a] = min(dp[a], j);
		}
	}


	for (int i = maxv-2; i >= 0; i--)
		dp[i] = min(dp[i], dp[i+1]);

	while (q--)
	{
		int x;
		scanf("%d", &x);

		if (prod <= x)
		{
			printf("oo\n");
			continue;
		}

		printf("%d\n", dp[x]);
	}
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~~
brunhilda.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &p[i]);
   ~~~~~^~~~~~~~~~~~~
brunhilda.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 39544 KB Output isn't correct
2 Incorrect 100 ms 39424 KB Output isn't correct
3 Incorrect 96 ms 39424 KB Output isn't correct
4 Incorrect 79 ms 39544 KB Output isn't correct
5 Incorrect 88 ms 39424 KB Output isn't correct
6 Incorrect 79 ms 39424 KB Output isn't correct
7 Incorrect 89 ms 39424 KB Output isn't correct
8 Incorrect 92 ms 39416 KB Output isn't correct
9 Incorrect 107 ms 39424 KB Output isn't correct
10 Incorrect 129 ms 39424 KB Output isn't correct
11 Incorrect 120 ms 39628 KB Output isn't correct
12 Incorrect 71 ms 39544 KB Output isn't correct
13 Incorrect 223 ms 39544 KB Output isn't correct
14 Incorrect 220 ms 39544 KB Output isn't correct
15 Incorrect 109 ms 39544 KB Output isn't correct
16 Incorrect 109 ms 39544 KB Output isn't correct
17 Incorrect 120 ms 39544 KB Output isn't correct
18 Incorrect 75 ms 39544 KB Output isn't correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 90 ms 39672 KB Output isn't correct
2 Incorrect 114 ms 40568 KB Output isn't correct
3 Incorrect 334 ms 40312 KB Output isn't correct
4 Incorrect 114 ms 39544 KB Output isn't correct
5 Incorrect 192 ms 40056 KB Output isn't correct
6 Incorrect 99 ms 39424 KB Output isn't correct
7 Incorrect 102 ms 39672 KB Output isn't correct
8 Incorrect 113 ms 39552 KB Output isn't correct
9 Incorrect 279 ms 40312 KB Output isn't correct
10 Incorrect 275 ms 40184 KB Output isn't correct
11 Incorrect 272 ms 40056 KB Output isn't correct
12 Incorrect 146 ms 39424 KB Output isn't correct
13 Incorrect 91 ms 39424 KB Output isn't correct
14 Incorrect 114 ms 39424 KB Output isn't correct
15 Incorrect 222 ms 39928 KB Output isn't correct
16 Incorrect 114 ms 40568 KB Output isn't correct
17 Incorrect 228 ms 39540 KB Output isn't correct
18 Incorrect 227 ms 40656 KB Output isn't correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 289 ms 40568 KB Output isn't correct
2 Incorrect 306 ms 40440 KB Output isn't correct
3 Incorrect 300 ms 40824 KB Output isn't correct
4 Incorrect 185 ms 40828 KB Output isn't correct
5 Incorrect 171 ms 42232 KB Output isn't correct
6 Incorrect 251 ms 40952 KB Output isn't correct
7 Incorrect 222 ms 41464 KB Output isn't correct
8 Incorrect 237 ms 40568 KB Output isn't correct
9 Incorrect 284 ms 40680 KB Output isn't correct
10 Incorrect 188 ms 39672 KB Output isn't correct
11 Incorrect 166 ms 40068 KB Output isn't correct
12 Incorrect 250 ms 40056 KB Output isn't correct
13 Incorrect 313 ms 41208 KB Output isn't correct
14 Incorrect 162 ms 41080 KB Output isn't correct
15 Incorrect 263 ms 39928 KB Output isn't correct
16 Incorrect 255 ms 40056 KB Output isn't correct
17 Incorrect 223 ms 40056 KB Output isn't correct
18 Incorrect 289 ms 40440 KB Output isn't correct
19 Incorrect 99 ms 39800 KB Output isn't correct
20 Incorrect 300 ms 40824 KB Output isn't correct
21 Incorrect 194 ms 41084 KB Output isn't correct
22 Incorrect 318 ms 42104 KB Output isn't correct
23 Incorrect 153 ms 41336 KB Output isn't correct
24 Incorrect 127 ms 40952 KB Output isn't correct
25 Incorrect 219 ms 41080 KB Output isn't correct
26 Incorrect 220 ms 40824 KB Output isn't correct
27 Incorrect 325 ms 41464 KB Output isn't correct
28 Incorrect 117 ms 41080 KB Output isn't correct
29 Incorrect 301 ms 42104 KB Output isn't correct
30 Incorrect 281 ms 41848 KB Output isn't correct
31 Incorrect 148 ms 40824 KB Output isn't correct
32 Incorrect 191 ms 40912 KB Output isn't correct
33 Incorrect 114 ms 40824 KB Output isn't correct
34 Incorrect 221 ms 41464 KB Output isn't correct
35 Incorrect 127 ms 41080 KB Output isn't correct
36 Incorrect 320 ms 42104 KB Output isn't correct
37 Incorrect 154 ms 42188 KB Output isn't correct
38 Incorrect 249 ms 40972 KB Output isn't correct
39 Incorrect 135 ms 41080 KB Output isn't correct
40 Incorrect 220 ms 40952 KB Output isn't correct
41 Incorrect 215 ms 41208 KB Output isn't correct
42 Incorrect 276 ms 41084 KB Output isn't correct