oj.uz

Submission #134089

# Submission time Handle Problem Language Result Execution time Memory
134089 2019-07-22T04:15:47 Z wilwxk Brunhilda’s Birthday (BOI13_brunhilda) C++14
47.4603 / 100
 1000 ms 40188 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-22); 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 212 ms 39584 KB Output is correct
2 Execution timed out 1046 ms 39472 KB Time limit exceeded
3 Correct 305 ms 39504 KB Output is correct
4 Execution timed out 1028 ms 39520 KB Time limit exceeded
5 Correct 554 ms 39696 KB Output is correct
6 Correct 210 ms 39492 KB Output is correct
7 Correct 311 ms 39556 KB Output is correct
8 Correct 354 ms 39492 KB Output is correct
9 Correct 669 ms 39552 KB Output is correct
10 Execution timed out 1077 ms 34312 KB Time limit exceeded
11 Execution timed out 1065 ms 35400 KB Time limit exceeded
12 Execution timed out 1029 ms 39544 KB Time limit exceeded
13 Execution timed out 1022 ms 39392 KB Time limit exceeded
14 Execution timed out 1037 ms 39500 KB Time limit exceeded
15 Execution timed out 1059 ms 39460 KB Time limit exceeded
16 Execution timed out 1055 ms 39488 KB Time limit exceeded
17 Execution timed out 1050 ms 39436 KB Time limit exceeded
18 Execution timed out 1028 ms 39516 KB Time limit exceeded

Subtask #2
11.1111111111 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 938 ms 39496 KB Output is correct
2 Correct 148 ms 39800 KB Output is correct
3 Correct 793 ms 39692 KB Output is correct
4 Execution timed out 1012 ms 39424 KB Time limit exceeded
5 Correct 900 ms 39676 KB Output is correct
6 Execution timed out 1016 ms 39552 KB Time limit exceeded
7 Correct 938 ms 39480 KB Output is correct
8 Execution timed out 1020 ms 39436 KB Time limit exceeded
9 Correct 903 ms 39748 KB Output is correct
10 Correct 792 ms 39772 KB Output is correct
11 Incorrect 939 ms 39612 KB Output isn't correct
12 Execution timed out 1022 ms 39456 KB Time limit exceeded
13 Correct 972 ms 39632 KB Output is correct
14 Execution timed out 1020 ms 39520 KB Time limit exceeded
15 Correct 955 ms 39680 KB Output is correct
16 Correct 148 ms 39800 KB Output is correct
17 Execution timed out 1034 ms 39416 KB Time limit exceeded
18 Incorrect 548 ms 39852 KB Output isn't correct

Subtask #3
28.5714285714 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 951 ms 39812 KB Output is correct
2 Correct 969 ms 39840 KB Output is correct
3 Correct 948 ms 39948 KB Output is correct
4 Execution timed out 1047 ms 39852 KB Time limit exceeded
5 Correct 632 ms 40000 KB Output is correct
6 Execution timed out 1050 ms 39972 KB Time limit exceeded
7 Correct 771 ms 40096 KB Output is correct
8 Correct 952 ms 39712 KB Output is correct
9 Correct 951 ms 39708 KB Output is correct
10 Execution timed out 1028 ms 39608 KB Time limit exceeded
11 Execution timed out 1025 ms 39672 KB Time limit exceeded
12 Execution timed out 1022 ms 39572 KB Time limit exceeded
13 Incorrect 976 ms 40088 KB Output isn't correct
14 Execution timed out 1070 ms 37936 KB Time limit exceeded
15 Execution timed out 1030 ms 39576 KB Time limit exceeded
16 Execution timed out 1038 ms 39672 KB Time limit exceeded
17 Correct 958 ms 39696 KB Output is correct
18 Correct 970 ms 39944 KB Output is correct
19 Correct 970 ms 39576 KB Output is correct
20 Correct 950 ms 39908 KB Output is correct
21 Execution timed out 1062 ms 40088 KB Time limit exceeded
22 Correct 932 ms 40188 KB Output is correct
23 Correct 966 ms 39892 KB Output is correct
24 Execution timed out 1057 ms 40008 KB Time limit exceeded
25 Execution timed out 1058 ms 39900 KB Time limit exceeded
26 Execution timed out 1053 ms 39800 KB Time limit exceeded
27 Correct 888 ms 40104 KB Output is correct
28 Execution timed out 1028 ms 39844 KB Time limit exceeded
29 Correct 929 ms 40072 KB Output is correct
30 Correct 987 ms 39980 KB Output is correct
31 Execution timed out 1031 ms 39796 KB Time limit exceeded
32 Execution timed out 1053 ms 39840 KB Time limit exceeded
33 Execution timed out 1040 ms 39768 KB Time limit exceeded
34 Correct 774 ms 40060 KB Output is correct
35 Execution timed out 1038 ms 39920 KB Time limit exceeded
36 Correct 935 ms 40096 KB Output is correct
37 Correct 633 ms 40124 KB Output is correct
38 Execution timed out 1050 ms 40084 KB Time limit exceeded
39 Execution timed out 1052 ms 39892 KB Time limit exceeded
40 Execution timed out 1040 ms 39852 KB Time limit exceeded
41 Correct 325 ms 40012 KB Output is correct
42 Execution timed out 1047 ms 40020 KB Time limit exceeded