Submission #46995

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
46995	2018-04-25T22:12:55 Z	rsalesc	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	17.7778 / 100	465 ms	139300 KB

brunhilda

#include <bits/stdc++.h>
using namespace std;

const int P = 1e6+10;
const int M = 1e5+10;
int mx;
vector<int> q[P];
int dp[P];

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].push_back(x);
	}

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

	for(int i = 0; i < P; i++) {
		for(int p : q[i]) {
			int nxt = i+p;
			int til = min(nxt, P);

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

			mx = max(mx, nxt);
			if(nxt < P) q[nxt].push_back(p);
		}
		q[i].clear();
	}

	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

17.7777777778 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	52 ms	33016 KB	Output is correct
2	Correct	114 ms	50584 KB	Output is correct
3	Correct	101 ms	50584 KB	Output is correct
4	Correct	54 ms	50584 KB	Output is correct
5	Correct	70 ms	50584 KB	Output is correct
6	Correct	45 ms	50584 KB	Output is correct
7	Correct	90 ms	50584 KB	Output is correct
8	Correct	120 ms	51600 KB	Output is correct
9	Correct	157 ms	53776 KB	Output is correct
10	Correct	174 ms	54584 KB	Output is correct
11	Correct	139 ms	54584 KB	Output is correct
12	Correct	39 ms	54584 KB	Output is correct
13	Correct	247 ms	57792 KB	Output is correct
14	Incorrect	258 ms	57792 KB	Output isn't correct
15	Correct	121 ms	57792 KB	Output is correct
16	Correct	121 ms	57792 KB	Output is correct
17	Incorrect	83 ms	57792 KB	Output isn't correct
18	Correct	58 ms	57792 KB	Output is correct

Subtask #2

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	93 ms	66468 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Runtime error	117 ms	70248 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
3	Incorrect	359 ms	95924 KB	Output isn't correct
4	Runtime error	145 ms	95924 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Incorrect	238 ms	97060 KB	Output isn't correct
6	Incorrect	129 ms	97060 KB	Output isn't correct
7	Runtime error	109 ms	97060 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Incorrect	110 ms	97060 KB	Output isn't correct
9	Incorrect	299 ms	97060 KB	Output isn't correct
10	Incorrect	393 ms	97060 KB	Output isn't correct
11	Incorrect	302 ms	97060 KB	Output isn't correct
12	Runtime error	190 ms	107028 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
13	Incorrect	77 ms	107028 KB	Output isn't correct
14	Incorrect	111 ms	107028 KB	Output isn't correct
15	Incorrect	268 ms	113068 KB	Output isn't correct
16	Runtime error	117 ms	113068 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Runtime error	250 ms	118280 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
18	Runtime error	269 ms	118824 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3

0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	275 ms	122104 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Runtime error	328 ms	124120 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
3	Runtime error	327 ms	124940 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
4	Runtime error	205 ms	124940 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Runtime error	129 ms	124940 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Runtime error	243 ms	124940 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Runtime error	211 ms	124940 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Runtime error	282 ms	126120 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Runtime error	283 ms	126608 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	185 ms	126608 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Runtime error	168 ms	126608 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
12	Runtime error	236 ms	126608 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
13	Incorrect	465 ms	126608 KB	Output isn't correct
14	Incorrect	326 ms	126608 KB	Output isn't correct
15	Runtime error	262 ms	126608 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
16	Runtime error	275 ms	127104 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Runtime error	257 ms	127104 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
18	Runtime error	315 ms	131336 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
19	Runtime error	120 ms	131336 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Runtime error	326 ms	132200 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
21	Incorrect	391 ms	132200 KB	Output isn't correct
22	Runtime error	326 ms	134640 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
23	Runtime error	129 ms	134640 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
24	Runtime error	96 ms	134640 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
25	Runtime error	197 ms	134640 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
26	Runtime error	202 ms	134640 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
27	Runtime error	375 ms	137764 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
28	Runtime error	117 ms	137764 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
29	Runtime error	265 ms	137764 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
30	Runtime error	260 ms	137764 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
31	Runtime error	133 ms	137764 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
32	Runtime error	143 ms	137764 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
33	Runtime error	81 ms	137764 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
34	Runtime error	228 ms	137764 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
35	Runtime error	126 ms	137764 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
36	Runtime error	312 ms	139300 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
37	Runtime error	138 ms	139300 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
38	Runtime error	251 ms	139300 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
39	Runtime error	113 ms	139300 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
40	Runtime error	225 ms	139300 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
41	Runtime error	243 ms	139300 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
42	Runtime error	298 ms	139300 KB	Execution killed with signal 11 (could be triggered by violating memory limits)