oj.uz

Submission #334737

# Submission time Handle Problem Language Result Execution time Memory
334737 2020-12-09T23:40:55 Z Fischer Brunhilda’s Birthday (BOI13_brunhilda) C++14
80.3175 / 100
 313 ms 80492 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e7 + 10;
int dp[maxn];
int link[maxn];

int main() {
	int m, q;
	scanf("%d%d", &m, &q);
	for (int i=0; i<m; ++i) {
		int x;
		scanf("%d", &x);
		for (int j=x-1; j<maxn; j+=x) {
			link[j] = x-1;
		}
	}
	for (int i = maxn-2; i >= 1; --i) {
		if (link[i] < link[i+1] - 1) {
			link[i] = link[i+1] - 1;
		}
	}
	const int inf = 1e9;
	for (int i = 1; i < maxn; ++i) {
			if (link[i] == 0) dp[i] = inf;
			else dp[i] = min(inf, dp[i - link[i]] + 1);
	}
	while (q--) {
		int n;
		scanf("%d", &n);
		if (dp[n] > n) puts("oo\n");
		else printf("%d\n", dp[n]);
	}
	return 0;
}

Compilation message

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 78700 KB Output is correct
2 Correct 112 ms 78572 KB Output is correct
3 Correct 102 ms 78572 KB Output is correct
4 Correct 94 ms 78700 KB Output is correct
5 Correct 107 ms 78560 KB Output is correct
6 Correct 100 ms 78572 KB Output is correct
7 Correct 100 ms 78572 KB Output is correct
8 Correct 108 ms 78572 KB Output is correct
9 Correct 126 ms 78572 KB Output is correct
10 Correct 139 ms 78580 KB Output is correct
11 Correct 133 ms 78720 KB Output is correct
12 Correct 93 ms 78572 KB Output is correct
13 Correct 225 ms 78696 KB Output is correct
14 Correct 221 ms 78828 KB Output is correct
15 Correct 124 ms 78572 KB Output is correct
16 Correct 112 ms 78572 KB Output is correct
17 Correct 114 ms 78720 KB Output is correct
18 Correct 95 ms 78700 KB Output is correct

Subtask #2
18.8888888889 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 78700 KB Output is correct
2 Correct 132 ms 79340 KB Output is correct
3 Correct 278 ms 79084 KB Output is correct
4 Correct 124 ms 78572 KB Output is correct
5 Correct 207 ms 78956 KB Output is correct
6 Correct 111 ms 78576 KB Output is correct
7 Correct 108 ms 78700 KB Output is correct
8 Correct 126 ms 78700 KB Output is correct
9 Correct 228 ms 79084 KB Output is correct
10 Correct 273 ms 79152 KB Output is correct
11 Incorrect 268 ms 78828 KB Output isn't correct
12 Correct 157 ms 78572 KB Output is correct
13 Correct 97 ms 78572 KB Output is correct
14 Correct 124 ms 78572 KB Output is correct
15 Correct 226 ms 78828 KB Output is correct
16 Correct 129 ms 79340 KB Output is correct
17 Correct 225 ms 78572 KB Output is correct
18 Correct 233 ms 79340 KB Output is correct

Subtask #3
41.4285714286 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 79340 KB Output is correct
2 Correct 285 ms 79340 KB Output is correct
3 Correct 285 ms 79596 KB Output is correct
4 Incorrect 191 ms 79596 KB Output isn't correct
5 Incorrect 169 ms 80492 KB Output isn't correct
6 Correct 247 ms 79724 KB Output is correct
7 Correct 221 ms 79884 KB Output is correct
8 Correct 237 ms 79340 KB Output is correct
9 Correct 239 ms 79340 KB Output is correct
10 Correct 185 ms 78828 KB Output is correct
11 Incorrect 164 ms 78848 KB Output isn't correct
12 Correct 211 ms 78956 KB Output is correct
13 Correct 279 ms 79852 KB Output is correct
14 Correct 175 ms 79980 KB Output is correct
15 Incorrect 221 ms 78956 KB Output isn't correct
16 Correct 246 ms 78828 KB Output is correct
17 Correct 225 ms 79084 KB Output is correct
18 Correct 285 ms 79212 KB Output is correct
19 Incorrect 110 ms 78828 KB Output isn't correct
20 Correct 288 ms 79596 KB Output is correct
21 Incorrect 196 ms 79980 KB Output isn't correct
22 Correct 307 ms 80256 KB Output is correct
23 Correct 162 ms 79852 KB Output is correct
24 Correct 136 ms 79596 KB Output is correct
25 Correct 209 ms 79724 KB Output is correct
26 Incorrect 190 ms 79596 KB Output isn't correct
27 Correct 313 ms 79852 KB Output is correct
28 Incorrect 130 ms 79724 KB Output isn't correct
29 Correct 295 ms 80364 KB Output is correct
30 Correct 270 ms 80236 KB Output is correct
31 Correct 150 ms 79596 KB Output is correct
32 Incorrect 163 ms 79596 KB Output isn't correct
33 Incorrect 125 ms 79500 KB Output isn't correct
34 Correct 221 ms 79852 KB Output is correct
35 Incorrect 135 ms 79724 KB Output isn't correct
36 Correct 301 ms 80236 KB Output is correct
37 Incorrect 165 ms 80364 KB Output isn't correct
38 Correct 244 ms 79596 KB Output is correct
39 Incorrect 148 ms 79724 KB Output isn't correct
40 Correct 217 ms 79596 KB Output is correct
41 Correct 197 ms 79852 KB Output is correct
42 Correct 262 ms 79852 KB Output is correct