oj.uz

Submission #134082

# Submission time Handle Problem Language Result Execution time Memory
134082 2019-07-22T04:09:04 Z wilwxk Brunhilda’s Birthday (BOI13_brunhilda) C++14
19.3651 / 100
 1000 ms 40824 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-25); 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 210 ms 39496 KB Output is correct
2 Execution timed out 1084 ms 36188 KB Time limit exceeded
3 Correct 305 ms 39488 KB Output is correct
4 Execution timed out 1082 ms 36984 KB Time limit exceeded
5 Correct 556 ms 39620 KB Output is correct
6 Correct 211 ms 39560 KB Output is correct
7 Correct 305 ms 39416 KB Output is correct
8 Correct 360 ms 39556 KB Output is correct
9 Correct 670 ms 39536 KB Output is correct
10 Execution timed out 1086 ms 34936 KB Time limit exceeded
11 Execution timed out 1073 ms 35964 KB Time limit exceeded
12 Execution timed out 1073 ms 36140 KB Time limit exceeded
13 Execution timed out 1079 ms 36600 KB Time limit exceeded
14 Execution timed out 1078 ms 36912 KB Time limit exceeded
15 Execution timed out 1075 ms 35044 KB Time limit exceeded
16 Execution timed out 1090 ms 36632 KB Time limit exceeded
17 Execution timed out 1083 ms 36472 KB Time limit exceeded
18 Execution timed out 1088 ms 37184 KB Time limit exceeded

Subtask #2
4.44444444444 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1058 ms 39616 KB Time limit exceeded
2 Correct 161 ms 39804 KB Output is correct
3 Correct 890 ms 39896 KB Output is correct
4 Execution timed out 1082 ms 37380 KB Time limit exceeded
5 Execution timed out 1024 ms 39692 KB Time limit exceeded
6 Execution timed out 1081 ms 37340 KB Time limit exceeded
7 Execution timed out 1057 ms 39544 KB Time limit exceeded
8 Execution timed out 1081 ms 37008 KB Time limit exceeded
9 Execution timed out 1034 ms 39780 KB Time limit exceeded
10 Correct 887 ms 39800 KB Output is correct
11 Execution timed out 1058 ms 39664 KB Time limit exceeded
12 Execution timed out 1074 ms 36800 KB Time limit exceeded
13 Execution timed out 1082 ms 38568 KB Time limit exceeded
14 Execution timed out 1080 ms 36924 KB Time limit exceeded
15 Execution timed out 1074 ms 39704 KB Time limit exceeded
16 Correct 162 ms 39800 KB Output is correct
17 Execution timed out 1070 ms 37108 KB Time limit exceeded
18 Incorrect 614 ms 39884 KB Output isn't correct

Subtask #3
7.14285714286 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1069 ms 39668 KB Time limit exceeded
2 Execution timed out 1073 ms 38500 KB Time limit exceeded
3 Execution timed out 1072 ms 39832 KB Time limit exceeded
4 Execution timed out 1083 ms 37624 KB Time limit exceeded
5 Correct 719 ms 40824 KB Output is correct
6 Execution timed out 1084 ms 37784 KB Time limit exceeded
7 Correct 865 ms 40440 KB Output is correct
8 Execution timed out 1065 ms 39952 KB Time limit exceeded
9 Execution timed out 1068 ms 39936 KB Time limit exceeded
10 Execution timed out 1074 ms 36996 KB Time limit exceeded
11 Execution timed out 1077 ms 37220 KB Time limit exceeded
12 Execution timed out 1076 ms 36340 KB Time limit exceeded
13 Execution timed out 1089 ms 40312 KB Time limit exceeded
14 Execution timed out 1084 ms 33828 KB Time limit exceeded
15 Execution timed out 1087 ms 37424 KB Time limit exceeded
16 Execution timed out 1084 ms 37368 KB Time limit exceeded
17 Execution timed out 1075 ms 39192 KB Time limit exceeded
18 Execution timed out 1083 ms 39600 KB Time limit exceeded
19 Execution timed out 1074 ms 39464 KB Time limit exceeded
20 Execution timed out 1071 ms 40184 KB Time limit exceeded
21 Execution timed out 1056 ms 35708 KB Time limit exceeded
22 Execution timed out 1040 ms 40748 KB Time limit exceeded
23 Execution timed out 1054 ms 39256 KB Time limit exceeded
24 Execution timed out 1068 ms 37004 KB Time limit exceeded
25 Execution timed out 1058 ms 36384 KB Time limit exceeded
26 Execution timed out 1047 ms 36108 KB Time limit exceeded
27 Execution timed out 1000 ms 40360 KB Time limit exceeded
28 Execution timed out 1066 ms 37212 KB Time limit exceeded
29 Execution timed out 1041 ms 40824 KB Time limit exceeded
30 Execution timed out 1070 ms 40292 KB Time limit exceeded
31 Execution timed out 1076 ms 37948 KB Time limit exceeded
32 Execution timed out 1074 ms 37056 KB Time limit exceeded
33 Execution timed out 1058 ms 36968 KB Time limit exceeded
34 Correct 867 ms 40200 KB Output is correct
35 Execution timed out 1075 ms 37192 KB Time limit exceeded
36 Execution timed out 1039 ms 40568 KB Time limit exceeded
37 Correct 708 ms 40776 KB Output is correct
38 Execution timed out 1072 ms 37080 KB Time limit exceeded
39 Execution timed out 1074 ms 37244 KB Time limit exceeded
40 Execution timed out 1049 ms 36560 KB Time limit exceeded
41 Correct 380 ms 40104 KB Output is correct
42 Execution timed out 1086 ms 36700 KB Time limit exceeded