Submission #283168

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
283168	2020-08-25T10:48:34 Z	theStaticMind	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	19.5238 / 100	1000 ms	40032 KB

brunhilda

#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
//#define int long long int
using namespace std;

int dp[10000001];

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int m, q;
	cin >> m >> q;

	vector<int> P(m);
	for(int i = 0; i < m; i++) cin >> P[i];

	for(int i = 1; i <= 1e7; i++) dp[i] = 1e9;
	
	for(int i = 1; i <= 1e7; i++){
		int c = 0;
		for(int j = m - 1; j >= 0 && c < P[j] - 1; j--){
			c = max(c, i % P[j]);
		}
		if(c) dp[i] = dp[i - c] + 1;
		else break;
	}

	while(q--){
		int n;
		cin >> n;

		if(dp[n] >= 1e9) cout << "oo\n";
		else cout << dp[n] << "\n";
	}
}

Subtask #1
16.6666666667 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	39416 KB	Output is correct
2	Correct	655 ms	39516 KB	Output is correct
3	Correct	30 ms	39424 KB	Output is correct
4	Correct	604 ms	39640 KB	Output is correct
5	Correct	356 ms	39416 KB	Output is correct
6	Correct	25 ms	39424 KB	Output is correct
7	Correct	28 ms	39416 KB	Output is correct
8	Correct	38 ms	39420 KB	Output is correct
9	Correct	215 ms	39544 KB	Output is correct
10	Correct	234 ms	39416 KB	Output is correct
11	Correct	254 ms	39416 KB	Output is correct
12	Execution timed out	1094 ms	39424 KB	Time limit exceeded
13	Execution timed out	1098 ms	39416 KB	Time limit exceeded
14	Execution timed out	1087 ms	39420 KB	Time limit exceeded
15	Correct	493 ms	39520 KB	Output is correct
16	Correct	669 ms	39516 KB	Output is correct
17	Correct	491 ms	39520 KB	Output is correct
18	Correct	603 ms	39544 KB	Output is correct

Subtask #2
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1103 ms	39544 KB	Time limit exceeded
2	Execution timed out	1088 ms	39800 KB	Time limit exceeded
3	Execution timed out	1101 ms	39808 KB	Time limit exceeded
4	Execution timed out	1097 ms	39416 KB	Time limit exceeded
5	Execution timed out	1043 ms	39672 KB	Time limit exceeded
6	Execution timed out	1087 ms	39416 KB	Time limit exceeded
7	Execution timed out	1064 ms	39548 KB	Time limit exceeded
8	Execution timed out	1099 ms	39416 KB	Time limit exceeded
9	Execution timed out	1093 ms	39800 KB	Time limit exceeded
10	Execution timed out	1096 ms	39808 KB	Time limit exceeded
11	Execution timed out	1100 ms	39680 KB	Time limit exceeded
12	Execution timed out	1096 ms	39424 KB	Time limit exceeded
13	Execution timed out	1080 ms	39416 KB	Time limit exceeded
14	Execution timed out	1084 ms	39424 KB	Time limit exceeded
15	Execution timed out	1084 ms	39672 KB	Time limit exceeded
16	Execution timed out	1086 ms	39800 KB	Time limit exceeded
17	Execution timed out	1102 ms	39416 KB	Time limit exceeded
18	Execution timed out	1031 ms	39808 KB	Time limit exceeded

Subtask #3
2.85714285714 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1077 ms	39672 KB	Time limit exceeded
2	Execution timed out	1100 ms	39680 KB	Time limit exceeded
3	Execution timed out	1082 ms	39680 KB	Time limit exceeded
4	Execution timed out	1081 ms	39424 KB	Time limit exceeded
5	Execution timed out	1092 ms	39800 KB	Time limit exceeded
6	Execution timed out	1102 ms	39552 KB	Time limit exceeded
7	Execution timed out	1100 ms	39808 KB	Time limit exceeded
8	Execution timed out	1090 ms	39680 KB	Time limit exceeded
9	Execution timed out	1096 ms	39680 KB	Time limit exceeded
10	Execution timed out	1083 ms	39424 KB	Time limit exceeded
11	Execution timed out	1097 ms	39424 KB	Time limit exceeded
12	Execution timed out	1089 ms	39552 KB	Time limit exceeded
13	Execution timed out	1096 ms	39544 KB	Time limit exceeded
14	Correct	428 ms	40032 KB	Output is correct
15	Execution timed out	1080 ms	39424 KB	Time limit exceeded
16	Execution timed out	1095 ms	39552 KB	Time limit exceeded
17	Execution timed out	1094 ms	39672 KB	Time limit exceeded
18	Execution timed out	1052 ms	39800 KB	Time limit exceeded
19	Execution timed out	1045 ms	39424 KB	Time limit exceeded
20	Execution timed out	1086 ms	39680 KB	Time limit exceeded
21	Correct	450 ms	40032 KB	Output is correct
22	Execution timed out	1036 ms	39808 KB	Time limit exceeded
23	Execution timed out	1102 ms	39552 KB	Time limit exceeded
24	Execution timed out	1086 ms	39416 KB	Time limit exceeded
25	Execution timed out	1095 ms	39416 KB	Time limit exceeded
26	Execution timed out	1093 ms	39424 KB	Time limit exceeded
27	Execution timed out	1097 ms	39800 KB	Time limit exceeded
28	Execution timed out	1088 ms	39544 KB	Time limit exceeded
29	Execution timed out	1098 ms	39800 KB	Time limit exceeded
30	Execution timed out	1098 ms	39800 KB	Time limit exceeded
31	Execution timed out	1095 ms	39424 KB	Time limit exceeded
32	Execution timed out	1098 ms	39424 KB	Time limit exceeded
33	Execution timed out	1041 ms	39424 KB	Time limit exceeded
34	Execution timed out	1098 ms	39800 KB	Time limit exceeded
35	Execution timed out	1083 ms	39424 KB	Time limit exceeded
36	Execution timed out	1095 ms	39804 KB	Time limit exceeded
37	Execution timed out	1100 ms	39800 KB	Time limit exceeded
38	Execution timed out	1094 ms	39544 KB	Time limit exceeded
39	Execution timed out	1053 ms	39424 KB	Time limit exceeded
40	Execution timed out	1097 ms	39544 KB	Time limit exceeded
41	Execution timed out	1047 ms	39800 KB	Time limit exceeded
42	Execution timed out	1097 ms	39424 KB	Time limit exceeded

Submission #283168

Compilation message

Subtask #1 16.6666666667 / 20.0

Subtask #2 0 / 20.0

Subtask #3 2.85714285714 / 60.0

Subtask #1
16.6666666667 / 20.0

Subtask #2
0 / 20.0

Subtask #3
2.85714285714 / 60.0