답안 #44318 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
44318	2018-03-31T11:24:59 Z	neutron_byte	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	17.7778 / 100	1000 ms	113896 KB

brunhilda

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

const int n = 1000 * 1000;

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;

    int updated[m];
    fill(updated, updated + m, 0);

    vector<int> current[n + 1];
    for (int i = 0; i < m; ++i) {
        for (int j = 1; prime[i] * j <= n; ++j) {
            current[prime[i] * j].push_back(i);
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int pIdx : current[i]) {
            updated[pIdx] = i;
        }

        int bestVal = INF;
        for (int j = 0; j < m; ++j) {
            bestVal = min(bestVal, updated[j]);
        }

        if (bestVal >= i) dp[i] = INF;
        else dp[i] = 1 + dp[bestVal];
    }

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

    return 0;
}

Subtask #1
17.7777777778 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	77 ms	33016 KB	Output is correct
2	Correct	204 ms	50528 KB	Output is correct
3	Correct	107 ms	50528 KB	Output is correct
4	Correct	150 ms	50528 KB	Output is correct
5	Correct	95 ms	50528 KB	Output is correct
6	Correct	73 ms	50528 KB	Output is correct
7	Correct	116 ms	50528 KB	Output is correct
8	Correct	158 ms	51408 KB	Output is correct
9	Correct	178 ms	53796 KB	Output is correct
10	Correct	230 ms	54612 KB	Output is correct
11	Correct	242 ms	54612 KB	Output is correct
12	Correct	138 ms	54612 KB	Output is correct
13	Execution timed out	1087 ms	56616 KB	Time limit exceeded
14	Execution timed out	1075 ms	56616 KB	Time limit exceeded
15	Correct	179 ms	56616 KB	Output is correct
16	Correct	192 ms	56616 KB	Output is correct
17	Correct	182 ms	56616 KB	Output is correct
18	Correct	150 ms	56616 KB	Output is correct

Subtask #2
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1058 ms	56616 KB	Time limit exceeded
2	Execution timed out	1083 ms	56616 KB	Time limit exceeded
3	Execution timed out	1085 ms	56616 KB	Time limit exceeded
4	Execution timed out	1094 ms	56616 KB	Time limit exceeded
5	Execution timed out	1082 ms	56616 KB	Time limit exceeded
6	Execution timed out	1081 ms	56616 KB	Time limit exceeded
7	Execution timed out	1085 ms	56616 KB	Time limit exceeded
8	Execution timed out	1073 ms	56616 KB	Time limit exceeded
9	Execution timed out	1090 ms	56616 KB	Time limit exceeded
10	Execution timed out	1085 ms	56616 KB	Time limit exceeded
11	Execution timed out	1084 ms	56616 KB	Time limit exceeded
12	Execution timed out	1084 ms	56616 KB	Time limit exceeded
13	Execution timed out	1076 ms	56616 KB	Time limit exceeded
14	Execution timed out	1083 ms	56616 KB	Time limit exceeded
15	Execution timed out	1085 ms	56616 KB	Time limit exceeded
16	Execution timed out	1078 ms	56616 KB	Time limit exceeded
17	Execution timed out	1089 ms	56616 KB	Time limit exceeded
18	Execution timed out	1098 ms	56616 KB	Time limit exceeded

Subtask #3
0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1077 ms	56616 KB	Time limit exceeded
2	Execution timed out	1084 ms	56616 KB	Time limit exceeded
3	Execution timed out	1087 ms	56616 KB	Time limit exceeded
4	Execution timed out	1083 ms	56616 KB	Time limit exceeded
5	Execution timed out	1088 ms	56616 KB	Time limit exceeded
6	Execution timed out	1068 ms	56616 KB	Time limit exceeded
7	Execution timed out	1087 ms	56616 KB	Time limit exceeded
8	Execution timed out	1088 ms	56616 KB	Time limit exceeded
9	Execution timed out	1090 ms	56616 KB	Time limit exceeded
10	Execution timed out	1088 ms	56616 KB	Time limit exceeded
11	Execution timed out	1091 ms	56616 KB	Time limit exceeded
12	Execution timed out	1092 ms	56616 KB	Time limit exceeded
13	Execution timed out	1091 ms	56616 KB	Time limit exceeded
14	Incorrect	443 ms	56632 KB	Output isn't correct
15	Execution timed out	1088 ms	56632 KB	Time limit exceeded
16	Execution timed out	1086 ms	56632 KB	Time limit exceeded
17	Execution timed out	1090 ms	56632 KB	Time limit exceeded
18	Execution timed out	1094 ms	56632 KB	Time limit exceeded
19	Execution timed out	1071 ms	56632 KB	Time limit exceeded
20	Execution timed out	1084 ms	56656 KB	Time limit exceeded
21	Runtime error	415 ms	113508 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
22	Execution timed out	1095 ms	113508 KB	Time limit exceeded
23	Execution timed out	1090 ms	113508 KB	Time limit exceeded
24	Execution timed out	1089 ms	113508 KB	Time limit exceeded
25	Execution timed out	1077 ms	113508 KB	Time limit exceeded
26	Execution timed out	1096 ms	113508 KB	Time limit exceeded
27	Execution timed out	1088 ms	113896 KB	Time limit exceeded
28	Runtime error	1037 ms	113896 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
29	Execution timed out	1100 ms	113896 KB	Time limit exceeded
30	Execution timed out	1093 ms	113896 KB	Time limit exceeded
31	Execution timed out	1080 ms	113896 KB	Time limit exceeded
32	Execution timed out	1093 ms	113896 KB	Time limit exceeded
33	Execution timed out	1072 ms	113896 KB	Time limit exceeded
34	Execution timed out	1080 ms	113896 KB	Time limit exceeded
35	Execution timed out	1090 ms	113896 KB	Time limit exceeded
36	Execution timed out	1087 ms	113896 KB	Time limit exceeded
37	Execution timed out	1080 ms	113896 KB	Time limit exceeded
38	Execution timed out	1087 ms	113896 KB	Time limit exceeded
39	Execution timed out	1071 ms	113896 KB	Time limit exceeded
40	Execution timed out	1089 ms	113896 KB	Time limit exceeded
41	Execution timed out	1083 ms	113896 KB	Time limit exceeded
42	Execution timed out	1080 ms	113896 KB	Time limit exceeded

답안 #44318

Compilation message

Subtask #1 17.7777777778 / 20.0

Subtask #2 0 / 20.0

Subtask #3 0 / 60.0

Subtask #1
17.7777777778 / 20.0

Subtask #2
0 / 20.0

Subtask #3
0 / 60.0