oj.uz

Submission #46999

# Submission time Handle Problem Language Result Execution time Memory
46999 2018-04-25T22:32:53 Z rsalesc Brunhilda’s Birthday (BOI13_brunhilda) C++14
25.873 / 100
 1000 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

const int P = 1e7+10;
const int M = 1e5+10;

struct Node {
	int v;
	Node * nxt;
};

int mx;
Node * q[P];
int dp[P];

Node* add(Node * no, int x) {
	return new Node({x, no});
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int m, Q;
	cin >> m >> Q;

	for(int i = 0; i < m; i++) {
		int x;
		cin >> x;
		q[0] = add(q[0], x);
	}

	for(int i = 1; i < P; i++) dp[i] = 1e9+10;

	for(int i = 0; i < P; i++) {
		Node* cur = q[i];
		while(cur) {
			int p = cur->v;
			int nxt = i+p;
			int til = min(nxt, P);

			for(int j = max(mx, i+1); j < til; j++) {
				dp[j] = dp[i]+1;
			}

			mx = max(mx, nxt);
			if(nxt < P) q[nxt] = add(q[nxt], p);
			cur = cur->nxt;
		}
	}

	for(int i = 0; i < Q; i++) {
		int x;
		cin >> x;
		if(dp[x] > 1e9) cout << "oo" << endl;
		else cout << dp[x] << endl;
	}
}

Subtask #1
7.77777777778 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 173900 KB Output is correct
2 Execution timed out 1033 ms 262144 KB Time limit exceeded
3 Execution timed out 1081 ms 262144 KB Time limit exceeded
4 Correct 191 ms 262144 KB Output is correct
5 Correct 372 ms 262144 KB Output is correct
6 Correct 259 ms 262144 KB Output is correct
7 Execution timed out 1120 ms 262144 KB Time limit exceeded
8 Execution timed out 1047 ms 262144 KB Time limit exceeded
9 Execution timed out 1111 ms 262144 KB Time limit exceeded
10 Execution timed out 1105 ms 262144 KB Time limit exceeded
11 Execution timed out 1083 ms 262144 KB Time limit exceeded
12 Correct 176 ms 262144 KB Output is correct
13 Execution timed out 1105 ms 262144 KB Time limit exceeded
14 Execution timed out 1111 ms 262144 KB Time limit exceeded
15 Execution timed out 1086 ms 262144 KB Time limit exceeded
16 Execution timed out 1101 ms 262144 KB Time limit exceeded
17 Correct 395 ms 262144 KB Output is correct
18 Correct 205 ms 262144 KB Output is correct

Subtask #2
6.66666666667 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 262144 KB Output is correct
2 Correct 501 ms 262144 KB Output is correct
3 Execution timed out 1115 ms 262144 KB Time limit exceeded
4 Execution timed out 1040 ms 262144 KB Time limit exceeded
5 Execution timed out 1076 ms 262144 KB Time limit exceeded
6 Execution timed out 1073 ms 262144 KB Time limit exceeded
7 Correct 414 ms 262144 KB Output is correct
8 Correct 488 ms 262144 KB Output is correct
9 Execution timed out 1082 ms 262144 KB Time limit exceeded
10 Execution timed out 1103 ms 262144 KB Time limit exceeded
11 Execution timed out 1108 ms 262144 KB Time limit exceeded
12 Execution timed out 1109 ms 262144 KB Time limit exceeded
13 Correct 373 ms 262144 KB Output is correct
14 Execution timed out 1062 ms 262144 KB Time limit exceeded
15 Execution timed out 1098 ms 262144 KB Time limit exceeded
16 Correct 531 ms 262144 KB Output is correct
17 Execution timed out 1100 ms 262144 KB Time limit exceeded
18 Execution timed out 1090 ms 262144 KB Time limit exceeded

Subtask #3
11.4285714286 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1097 ms 262144 KB Time limit exceeded
2 Execution timed out 1110 ms 262144 KB Time limit exceeded
3 Execution timed out 1113 ms 262144 KB Time limit exceeded
4 Execution timed out 1102 ms 262144 KB Time limit exceeded
5 Correct 844 ms 262144 KB Output is correct
6 Execution timed out 1112 ms 262144 KB Time limit exceeded
7 Execution timed out 1061 ms 262144 KB Time limit exceeded
8 Execution timed out 1095 ms 262144 KB Time limit exceeded
9 Execution timed out 1068 ms 262144 KB Time limit exceeded
10 Execution timed out 1105 ms 262144 KB Time limit exceeded
11 Execution timed out 1100 ms 262144 KB Time limit exceeded
12 Execution timed out 1108 ms 262144 KB Time limit exceeded
13 Execution timed out 1096 ms 262144 KB Time limit exceeded
14 Execution timed out 1108 ms 262144 KB Time limit exceeded
15 Execution timed out 1110 ms 262144 KB Time limit exceeded
16 Execution timed out 1102 ms 262144 KB Time limit exceeded
17 Execution timed out 1049 ms 262144 KB Time limit exceeded
18 Execution timed out 1115 ms 262144 KB Time limit exceeded
19 Execution timed out 1037 ms 262144 KB Time limit exceeded
20 Execution timed out 1115 ms 262144 KB Time limit exceeded
21 Execution timed out 1114 ms 262144 KB Time limit exceeded
22 Execution timed out 1087 ms 262144 KB Time limit exceeded
23 Correct 832 ms 262144 KB Output is correct
24 Correct 447 ms 262144 KB Output is correct
25 Execution timed out 1115 ms 262144 KB Time limit exceeded
26 Execution timed out 1120 ms 262144 KB Time limit exceeded
27 Execution timed out 1105 ms 262144 KB Time limit exceeded
28 Correct 605 ms 262144 KB Output is correct
29 Execution timed out 1077 ms 262144 KB Time limit exceeded
30 Execution timed out 1081 ms 262144 KB Time limit exceeded
31 Execution timed out 1052 ms 262144 KB Time limit exceeded
32 Execution timed out 1070 ms 262144 KB Time limit exceeded
33 Correct 389 ms 262144 KB Output is correct
34 Execution timed out 1042 ms 262144 KB Time limit exceeded
35 Correct 641 ms 262144 KB Output is correct
36 Execution timed out 1098 ms 262144 KB Time limit exceeded
37 Correct 773 ms 262144 KB Output is correct
38 Execution timed out 1097 ms 262144 KB Time limit exceeded
39 Correct 538 ms 262144 KB Output is correct
40 Execution timed out 1114 ms 262144 KB Time limit exceeded
41 Execution timed out 1096 ms 262144 KB Time limit exceeded
42 Execution timed out 1110 ms 262144 KB Time limit exceeded