oj.uz

Submission #134090

# Submission time Handle Problem Language Result Execution time Memory
134090 2019-07-22T04:17:14 Z wilwxk Brunhilda’s Birthday (BOI13_brunhilda) C++14
34.9206 / 100
 1000 ms 40184 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-23); 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 214 ms 39416 KB Output is correct
2 Execution timed out 1069 ms 37016 KB Time limit exceeded
3 Correct 305 ms 39544 KB Output is correct
4 Execution timed out 1072 ms 37152 KB Time limit exceeded
5 Correct 558 ms 39588 KB Output is correct
6 Correct 210 ms 39416 KB Output is correct
7 Correct 305 ms 39440 KB Output is correct
8 Correct 354 ms 39516 KB Output is correct
9 Correct 667 ms 39596 KB Output is correct
10 Execution timed out 1068 ms 33464 KB Time limit exceeded
11 Execution timed out 1081 ms 35972 KB Time limit exceeded
12 Execution timed out 1088 ms 37796 KB Time limit exceeded
13 Execution timed out 1064 ms 37384 KB Time limit exceeded
14 Execution timed out 1086 ms 38264 KB Time limit exceeded
15 Execution timed out 1086 ms 37712 KB Time limit exceeded
16 Execution timed out 1075 ms 37168 KB Time limit exceeded
17 Execution timed out 1081 ms 37048 KB Time limit exceeded
18 Execution timed out 1082 ms 37552 KB Time limit exceeded

Subtask #2
10.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 985 ms 39572 KB Output is correct
2 Correct 152 ms 39776 KB Output is correct
3 Correct 827 ms 39684 KB Output is correct
4 Execution timed out 1081 ms 39644 KB Time limit exceeded
5 Correct 949 ms 39740 KB Output is correct
6 Execution timed out 1085 ms 39428 KB Time limit exceeded
7 Correct 983 ms 39600 KB Output is correct
8 Execution timed out 1074 ms 38564 KB Time limit exceeded
9 Correct 948 ms 39756 KB Output is correct
10 Correct 831 ms 39740 KB Output is correct
11 Incorrect 999 ms 39536 KB Output isn't correct
12 Execution timed out 1045 ms 37580 KB Time limit exceeded
13 Execution timed out 1033 ms 39480 KB Time limit exceeded
14 Execution timed out 1063 ms 38304 KB Time limit exceeded
15 Correct 1000 ms 39576 KB Output is correct
16 Correct 152 ms 39760 KB Output is correct
17 Execution timed out 1083 ms 39148 KB Time limit exceeded
18 Incorrect 580 ms 39820 KB Output isn't correct

Subtask #3
17.1428571429 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 993 ms 39740 KB Output is correct
2 Execution timed out 1022 ms 39736 KB Time limit exceeded
3 Execution timed out 1002 ms 39852 KB Time limit exceeded
4 Execution timed out 1036 ms 37312 KB Time limit exceeded
5 Correct 667 ms 39980 KB Output is correct
6 Execution timed out 1075 ms 39304 KB Time limit exceeded
7 Correct 805 ms 39892 KB Output is correct
8 Correct 996 ms 39868 KB Output is correct
9 Correct 991 ms 39864 KB Output is correct
10 Execution timed out 1076 ms 38548 KB Time limit exceeded
11 Execution timed out 1070 ms 38492 KB Time limit exceeded
12 Execution timed out 1072 ms 38240 KB Time limit exceeded
13 Execution timed out 1031 ms 39824 KB Time limit exceeded
14 Execution timed out 1086 ms 36544 KB Time limit exceeded
15 Execution timed out 1069 ms 38604 KB Time limit exceeded
16 Execution timed out 1070 ms 38580 KB Time limit exceeded
17 Execution timed out 1016 ms 39656 KB Time limit exceeded
18 Execution timed out 1020 ms 39768 KB Time limit exceeded
19 Execution timed out 1012 ms 39548 KB Time limit exceeded
20 Execution timed out 1002 ms 39836 KB Time limit exceeded
21 Execution timed out 1067 ms 36716 KB Time limit exceeded
22 Correct 975 ms 40132 KB Output is correct
23 Execution timed out 1041 ms 39928 KB Time limit exceeded
24 Execution timed out 1071 ms 37968 KB Time limit exceeded
25 Execution timed out 1082 ms 39160 KB Time limit exceeded
26 Execution timed out 1084 ms 39380 KB Time limit exceeded
27 Correct 931 ms 40176 KB Output is correct
28 Execution timed out 1081 ms 39672 KB Time limit exceeded
29 Correct 967 ms 40184 KB Output is correct
30 Execution timed out 1024 ms 40104 KB Time limit exceeded
31 Execution timed out 1079 ms 39632 KB Time limit exceeded
32 Execution timed out 1070 ms 39072 KB Time limit exceeded
33 Execution timed out 1069 ms 39168 KB Time limit exceeded
34 Correct 817 ms 40024 KB Output is correct
35 Execution timed out 1070 ms 38836 KB Time limit exceeded
36 Correct 977 ms 40184 KB Output is correct
37 Correct 659 ms 40068 KB Output is correct
38 Execution timed out 1082 ms 39544 KB Time limit exceeded
39 Execution timed out 1083 ms 39596 KB Time limit exceeded
40 Execution timed out 1080 ms 39716 KB Time limit exceeded
41 Correct 337 ms 40016 KB Output is correct
42 Execution timed out 1082 ms 38916 KB Time limit exceeded