oj.uz

Submission #163972

# Submission time Handle Problem Language Result Execution time Memory
163972 2019-11-16T12:52:53 Z luciocf Brunhilda’s Birthday (BOI13_brunhilda) C++14
8.09524 / 100
 476 ms 41476 KB 
#include <bits/stdc++.h>

using namespace std;

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

int a[maxn];

int dp[maxv];

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

	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);

	int P = a[n];
	long long prod = 1ll;

	for (int i = 1; i <= n; i++)
		if (prod < maxv)
			prod = 1ll*prod*a[i];

	for (int i = 1; i < maxv; i++)
		dp[i] = inf;

	dp[1] = 1;
	for (int i = 2; i < maxv; i++)
	{
		if (i%prod == 0) continue;

		if ((i-1)%prod == 0)
		{
			for (int j = n; j >= 1; j--)
				if (i%a[j])
					dp[i] = min(dp[i], dp[i-(i%a[j])]);
		}
		else if (i%P == 0 || (i-1)%P == 0) dp[i] = dp[i-1]+1;
		else dp[i] = dp[i-1];
	}

	for (int i = 1; i <= q; i++)
	{
		int x;
		scanf("%d", &x);

		if (dp[x] == inf) printf("oo\n");
		else printf("%d\n", dp[x]);
	}
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:16: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:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[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
1.11111111111 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 349 ms 39516 KB Output isn't correct
2 Incorrect 351 ms 39416 KB Output isn't correct
3 Incorrect 353 ms 39544 KB Output isn't correct
4 Incorrect 417 ms 39416 KB Output isn't correct
5 Incorrect 352 ms 39672 KB Output isn't correct
6 Incorrect 351 ms 39416 KB Output isn't correct
7 Incorrect 350 ms 39544 KB Output isn't correct
8 Incorrect 351 ms 39416 KB Output isn't correct
9 Incorrect 351 ms 39600 KB Output isn't correct
10 Incorrect 352 ms 39420 KB Output isn't correct
11 Incorrect 350 ms 39416 KB Output isn't correct
12 Correct 354 ms 39416 KB Output is correct
13 Incorrect 360 ms 39544 KB Output isn't correct
14 Incorrect 362 ms 39544 KB Output isn't correct
15 Incorrect 351 ms 39416 KB Output isn't correct
16 Incorrect 351 ms 39416 KB Output isn't correct
17 Incorrect 353 ms 39544 KB Output isn't correct
18 Incorrect 359 ms 39416 KB Output isn't correct

Subtask #2
5.55555555556 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 358 ms 39640 KB Output isn't correct
2 Correct 368 ms 40344 KB Output is correct
3 Correct 375 ms 40028 KB Output is correct
4 Incorrect 358 ms 39548 KB Output isn't correct
5 Correct 386 ms 39928 KB Output is correct
6 Incorrect 356 ms 39416 KB Output isn't correct
7 Incorrect 399 ms 39544 KB Output isn't correct
8 Incorrect 376 ms 39672 KB Output isn't correct
9 Incorrect 364 ms 40056 KB Output isn't correct
10 Correct 382 ms 40040 KB Output is correct
11 Incorrect 360 ms 39672 KB Output isn't correct
12 Incorrect 361 ms 39416 KB Output isn't correct
13 Incorrect 359 ms 39544 KB Output isn't correct
14 Incorrect 360 ms 39416 KB Output isn't correct
15 Incorrect 363 ms 39672 KB Output isn't correct
16 Correct 372 ms 40440 KB Output is correct
17 Incorrect 360 ms 39544 KB Output isn't correct
18 Incorrect 368 ms 40312 KB Output isn't correct

Subtask #3
1.42857142857 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 377 ms 40180 KB Output isn't correct
2 Incorrect 372 ms 40028 KB Output isn't correct
3 Incorrect 376 ms 40440 KB Output isn't correct
4 Incorrect 394 ms 40440 KB Output isn't correct
5 Incorrect 402 ms 41336 KB Output isn't correct
6 Incorrect 398 ms 40312 KB Output isn't correct
7 Incorrect 383 ms 40916 KB Output isn't correct
8 Incorrect 379 ms 40184 KB Output isn't correct
9 Incorrect 380 ms 40312 KB Output isn't correct
10 Incorrect 397 ms 39544 KB Output isn't correct
11 Incorrect 476 ms 39800 KB Output isn't correct
12 Incorrect 379 ms 39648 KB Output isn't correct
13 Incorrect 385 ms 40540 KB Output isn't correct
14 Incorrect 373 ms 40936 KB Output isn't correct
15 Incorrect 367 ms 39672 KB Output isn't correct
16 Incorrect 381 ms 39772 KB Output isn't correct
17 Incorrect 435 ms 39800 KB Output isn't correct
18 Incorrect 386 ms 40056 KB Output isn't correct
19 Incorrect 368 ms 39772 KB Output isn't correct
20 Incorrect 379 ms 40440 KB Output isn't correct
21 Incorrect 389 ms 40952 KB Output isn't correct
22 Incorrect 409 ms 41476 KB Output isn't correct
23 Incorrect 398 ms 40680 KB Output isn't correct
24 Incorrect 412 ms 40568 KB Output isn't correct
25 Incorrect 399 ms 40440 KB Output isn't correct
26 Incorrect 406 ms 40316 KB Output isn't correct
27 Incorrect 389 ms 40800 KB Output isn't correct
28 Incorrect 395 ms 40668 KB Output isn't correct
29 Incorrect 415 ms 41332 KB Output isn't correct
30 Incorrect 407 ms 41064 KB Output isn't correct
31 Incorrect 398 ms 40312 KB Output isn't correct
32 Incorrect 396 ms 40440 KB Output isn't correct
33 Incorrect 398 ms 40400 KB Output isn't correct
34 Incorrect 384 ms 40952 KB Output isn't correct
35 Incorrect 392 ms 40696 KB Output isn't correct
36 Incorrect 409 ms 41416 KB Output isn't correct
37 Incorrect 409 ms 41344 KB Output isn't correct
38 Incorrect 399 ms 40460 KB Output isn't correct
39 Incorrect 400 ms 40548 KB Output isn't correct
40 Incorrect 417 ms 40300 KB Output isn't correct
41 Correct 384 ms 40960 KB Output is correct
42 Incorrect 386 ms 40568 KB Output isn't correct