oj.uz

Submission #134079

# Submission time Handle Problem Language Result Execution time Memory
134079 2019-07-22T04:04:10 Z wilwxk Brunhilda’s Birthday (BOI13_brunhilda) C++14
11.4286 / 100
 1000 ms 41192 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN=1e5+5;
const int MAXX=1e7+3;
const int INF=1e9;
int v[MAXN];
int dp[MAXX];
int n, q;

int main() {
	scanf("%d %d", &n, &q);
	for(int i=0; i<n; i++) scanf("%d", &v[i]);
	dp[0]=0;
	for(int i=1; i<v[n-1]; i++) dp[i]=1; 
	for(int i=v[n-1]; i<MAXX; i++) {
		dp[i]=INF;
		bool ok=0;
		for(int j=n-1; j>=max(0, n-50); j--) {
			if(i%v[j]==0) continue;
			int ind=i-(i%v[j]);
			dp[i]=min(dp[i], dp[ind]+1);
		}
	}

	// for(int i=0; i<MAXX; i++) printf("%d ", dp[i]);
	while(q--) {
		int a; scanf("%d", &a);
		if(dp[a]==-1||dp[a]>MAXN) printf("oo\n");
		else printf("%d\n", dp[a]);
	}

}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:18:8: warning: unused variable 'ok' [-Wunused-variable]
   bool ok=0;
        ^~
brunhilda.cpp:12: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:13:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<n; i++) scanf("%d", &v[i]);
                         ~~~~~^~~~~~~~~~~~~
brunhilda.cpp:28:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a; scanf("%d", &a);
          ~~~~~^~~~~~~~~~

Subtask #1
7.77777777778 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 39544 KB Output is correct
2 Execution timed out 1078 ms 21604 KB Time limit exceeded
3 Correct 314 ms 39512 KB Output is correct
4 Execution timed out 1069 ms 18928 KB Time limit exceeded
5 Correct 563 ms 39476 KB Output is correct
6 Correct 210 ms 39544 KB Output is correct
7 Correct 311 ms 39424 KB Output is correct
8 Correct 358 ms 39544 KB Output is correct
9 Correct 663 ms 39544 KB Output is correct
10 Execution timed out 1088 ms 34808 KB Time limit exceeded
11 Execution timed out 1087 ms 35856 KB Time limit exceeded
12 Execution timed out 1081 ms 19064 KB Time limit exceeded
13 Execution timed out 1084 ms 19212 KB Time limit exceeded
14 Execution timed out 1086 ms 19320 KB Time limit exceeded
15 Execution timed out 1067 ms 26744 KB Time limit exceeded
16 Execution timed out 1081 ms 22008 KB Time limit exceeded
17 Execution timed out 1083 ms 18288 KB Time limit exceeded
18 Execution timed out 1067 ms 18440 KB Time limit exceeded

Subtask #2
2.22222222222 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1084 ms 22756 KB Time limit exceeded
2 Correct 285 ms 40568 KB Output is correct
3 Execution timed out 1077 ms 28408 KB Time limit exceeded
4 Execution timed out 1054 ms 18640 KB Time limit exceeded
5 Execution timed out 1082 ms 24696 KB Time limit exceeded
6 Execution timed out 1080 ms 19448 KB Time limit exceeded
7 Execution timed out 1060 ms 22236 KB Time limit exceeded
8 Execution timed out 1078 ms 19192 KB Time limit exceeded
9 Execution timed out 1065 ms 24424 KB Time limit exceeded
10 Execution timed out 1082 ms 29176 KB Time limit exceeded
11 Execution timed out 1072 ms 22676 KB Time limit exceeded
12 Execution timed out 1072 ms 19268 KB Time limit exceeded
13 Execution timed out 1067 ms 20628 KB Time limit exceeded
14 Execution timed out 1079 ms 19448 KB Time limit exceeded
15 Execution timed out 1070 ms 22364 KB Time limit exceeded
16 Correct 275 ms 40588 KB Output is correct
17 Execution timed out 1080 ms 19376 KB Time limit exceeded
18 Execution timed out 1057 ms 38520 KB Time limit exceeded

Subtask #3
1.42857142857 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1071 ms 23164 KB Time limit exceeded
2 Execution timed out 1072 ms 22092 KB Time limit exceeded
3 Execution timed out 1078 ms 23340 KB Time limit exceeded
4 Execution timed out 1078 ms 19584 KB Time limit exceeded
5 Execution timed out 1069 ms 37136 KB Time limit exceeded
6 Execution timed out 1081 ms 19832 KB Time limit exceeded
7 Execution timed out 1080 ms 31112 KB Time limit exceeded
8 Execution timed out 1072 ms 23288 KB Time limit exceeded
9 Execution timed out 1072 ms 23184 KB Time limit exceeded
10 Execution timed out 1074 ms 19512 KB Time limit exceeded
11 Execution timed out 1074 ms 19472 KB Time limit exceeded
12 Execution timed out 1068 ms 19468 KB Time limit exceeded
13 Execution timed out 1047 ms 21556 KB Time limit exceeded
14 Execution timed out 1066 ms 24088 KB Time limit exceeded
15 Execution timed out 1075 ms 19320 KB Time limit exceeded
16 Execution timed out 1077 ms 19584 KB Time limit exceeded
17 Execution timed out 1070 ms 22496 KB Time limit exceeded
18 Execution timed out 1065 ms 22172 KB Time limit exceeded
19 Execution timed out 1074 ms 21700 KB Time limit exceeded
20 Execution timed out 1078 ms 23352 KB Time limit exceeded
21 Execution timed out 1074 ms 18668 KB Time limit exceeded
22 Execution timed out 1081 ms 25816 KB Time limit exceeded
23 Execution timed out 1076 ms 23308 KB Time limit exceeded
24 Execution timed out 1083 ms 19412 KB Time limit exceeded
25 Execution timed out 1069 ms 18852 KB Time limit exceeded
26 Execution timed out 1086 ms 19528 KB Time limit exceeded
27 Execution timed out 1072 ms 26284 KB Time limit exceeded
28 Execution timed out 1065 ms 19500 KB Time limit exceeded
29 Execution timed out 1067 ms 25696 KB Time limit exceeded
30 Execution timed out 1044 ms 22968 KB Time limit exceeded
31 Execution timed out 1063 ms 20076 KB Time limit exceeded
32 Execution timed out 1086 ms 19636 KB Time limit exceeded
33 Execution timed out 1071 ms 19632 KB Time limit exceeded
34 Execution timed out 1085 ms 31132 KB Time limit exceeded
35 Execution timed out 1064 ms 19396 KB Time limit exceeded
36 Execution timed out 1064 ms 25436 KB Time limit exceeded
37 Execution timed out 1080 ms 37208 KB Time limit exceeded
38 Execution timed out 1077 ms 19564 KB Time limit exceeded
39 Execution timed out 1069 ms 19212 KB Time limit exceeded
40 Execution timed out 1087 ms 20320 KB Time limit exceeded
41 Correct 654 ms 41192 KB Output is correct
42 Execution timed out 1078 ms 19460 KB Time limit exceeded