Submission #44300

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
44300	2018-03-31T10:46:19 Z	neutron_byte	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	17.7778 / 100	1000 ms	25848 KB

brunhilda

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

const int n = 10 * 1000 * 100;

int main() {
    int m, q, x;
    cin >> m >> q;

    int prime[m];
    for (int i = 0; i < m; ++i) {
        cin >> prime[i];
    }

    int dp[n + 1];
    dp[0] = 0;

    for (int i = 1; i <= n; ++i) {
        dp[i] = INF;
        for (int j = 0; j < m; ++j) {
            dp[i] = min(dp[i], 1 + dp[i - i % prime[j]]);
        }
    }

    while (q--) {
        cin >> x;
        cout << (dp[x] < INF ? to_string(dp[x]) : "oo") << endl;
    }

    return 0;
}

Subtask #1

17.7777777778 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	4216 KB	Output is correct
2	Correct	201 ms	4380 KB	Output is correct
3	Correct	33 ms	4496 KB	Output is correct
4	Correct	400 ms	4564 KB	Output is correct
5	Correct	51 ms	4564 KB	Output is correct
6	Correct	24 ms	4564 KB	Output is correct
7	Correct	33 ms	4636 KB	Output is correct
8	Correct	43 ms	4636 KB	Output is correct
9	Correct	50 ms	4636 KB	Output is correct
10	Correct	98 ms	4648 KB	Output is correct
11	Correct	98 ms	4712 KB	Output is correct
12	Correct	470 ms	4848 KB	Output is correct
13	Execution timed out	1086 ms	4848 KB	Time limit exceeded
14	Execution timed out	1086 ms	4848 KB	Time limit exceeded
15	Correct	146 ms	4848 KB	Output is correct
16	Correct	200 ms	4848 KB	Output is correct
17	Correct	259 ms	4924 KB	Output is correct
18	Correct	431 ms	4968 KB	Output is correct

Subtask #2

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1081 ms	4968 KB	Time limit exceeded
2	Execution timed out	1085 ms	4968 KB	Time limit exceeded
3	Execution timed out	1091 ms	4968 KB	Time limit exceeded
4	Execution timed out	1083 ms	4968 KB	Time limit exceeded
5	Execution timed out	1077 ms	4968 KB	Time limit exceeded
6	Execution timed out	1082 ms	4968 KB	Time limit exceeded
7	Execution timed out	1091 ms	4968 KB	Time limit exceeded
8	Execution timed out	1063 ms	4968 KB	Time limit exceeded
9	Execution timed out	1085 ms	4968 KB	Time limit exceeded
10	Execution timed out	1091 ms	4968 KB	Time limit exceeded
11	Execution timed out	1087 ms	4968 KB	Time limit exceeded
12	Execution timed out	1083 ms	4968 KB	Time limit exceeded
13	Execution timed out	1077 ms	4968 KB	Time limit exceeded
14	Execution timed out	1089 ms	4968 KB	Time limit exceeded
15	Execution timed out	1079 ms	4968 KB	Time limit exceeded
16	Execution timed out	1086 ms	5524 KB	Time limit exceeded
17	Execution timed out	1086 ms	5588 KB	Time limit exceeded
18	Execution timed out	1069 ms	6436 KB	Time limit exceeded

Subtask #3

0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1090 ms	6588 KB	Time limit exceeded
2	Execution timed out	1088 ms	7084 KB	Time limit exceeded
3	Execution timed out	1086 ms	7580 KB	Time limit exceeded
4	Execution timed out	1082 ms	7904 KB	Time limit exceeded
5	Execution timed out	1081 ms	8848 KB	Time limit exceeded
6	Execution timed out	1086 ms	8848 KB	Time limit exceeded
7	Execution timed out	1087 ms	9836 KB	Time limit exceeded
8	Execution timed out	1079 ms	10332 KB	Time limit exceeded
9	Execution timed out	1082 ms	10700 KB	Time limit exceeded
10	Execution timed out	1075 ms	10904 KB	Time limit exceeded
11	Execution timed out	1081 ms	10936 KB	Time limit exceeded
12	Execution timed out	1078 ms	10988 KB	Time limit exceeded
13	Execution timed out	1079 ms	11452 KB	Time limit exceeded
14	Runtime error	161 ms	19108 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Execution timed out	1080 ms	19108 KB	Time limit exceeded
16	Execution timed out	1082 ms	19108 KB	Time limit exceeded
17	Execution timed out	1083 ms	19108 KB	Time limit exceeded
18	Execution timed out	1078 ms	19108 KB	Time limit exceeded
19	Execution timed out	1084 ms	19108 KB	Time limit exceeded
20	Execution timed out	1084 ms	19108 KB	Time limit exceeded
21	Runtime error	482 ms	20920 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
22	Execution timed out	1079 ms	20920 KB	Time limit exceeded
23	Execution timed out	1081 ms	20920 KB	Time limit exceeded
24	Execution timed out	1092 ms	20920 KB	Time limit exceeded
25	Execution timed out	1085 ms	20920 KB	Time limit exceeded
26	Execution timed out	1082 ms	20920 KB	Time limit exceeded
27	Execution timed out	1089 ms	20920 KB	Time limit exceeded
28	Execution timed out	1089 ms	20920 KB	Time limit exceeded
29	Execution timed out	1071 ms	20920 KB	Time limit exceeded
30	Execution timed out	1082 ms	21300 KB	Time limit exceeded
31	Execution timed out	1083 ms	21432 KB	Time limit exceeded
32	Execution timed out	1088 ms	21580 KB	Time limit exceeded
33	Execution timed out	1078 ms	21872 KB	Time limit exceeded
34	Execution timed out	1091 ms	22452 KB	Time limit exceeded
35	Execution timed out	1076 ms	22692 KB	Time limit exceeded
36	Execution timed out	1090 ms	23516 KB	Time limit exceeded
37	Execution timed out	1087 ms	24256 KB	Time limit exceeded
38	Execution timed out	1081 ms	24524 KB	Time limit exceeded
39	Execution timed out	1081 ms	24568 KB	Time limit exceeded
40	Execution timed out	1083 ms	24592 KB	Time limit exceeded
41	Execution timed out	1078 ms	25772 KB	Time limit exceeded
42	Execution timed out	1088 ms	25848 KB	Time limit exceeded