oj.uz

답안 #242155

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
242155 2020-06-27T03:04:34 Z thecodingwizard Brunhilda’s Birthday (BOI13_brunhilda) C++11
5.55556 / 100
 1000 ms 262148 KB 
#include <bits/stdc++.h>

using namespace std;

#define ii pair<int, int>
#define f first
#define s second

int A[100000]; 
int dp[10000001]; 
vector<int> transitions[10000001];

int main() {
    int m, q; cin >> m >> q;
    for (int i = 0; i < m; i++) cin >> A[i];
    for (int i = 0; i < 1000001; i++) dp[i] = -1;
    dp[0] = 0;

    priority_queue<ii, vector<ii>, greater<ii>> pq;
    for (int i = 0; i < m; i++) {
        pq.push(make_pair(0, -A[i]));

        transitions[A[i]].push_back(A[i]);
    }

    while (!pq.empty()) {
        ii u = pq.top(); pq.pop();
        if (dp[u.f] == -1) continue;

        int mx = u.f - u.s;
        mx = min(mx, 10000001);
        for (int i = u.f + 1; i < mx; i++) {
            for (int x : transitions[i]) {
                pq.push({i, -x});
                if (i+x<10000001) transitions[i+x].push_back(x);
            }
            transitions[i].clear();
            if (dp[i] == -1) dp[i] = dp[u.f]+1;
        }

        // while (!pq.empty() && pq.top().f < mx) pq.pop();
    }

    for (int i = 0; i < q; i++) {
        int x; cin >> x;
        if (dp[x] == -1) cout << "oo" << "\n";
        else cout << dp[x] << "\n";
    }

    return 0;
}

Subtask #1
5.55555555556 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 239096 KB Output is correct
2 Runtime error 367 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Correct 158 ms 244216 KB Output is correct
4 Execution timed out 1105 ms 255352 KB Time limit exceeded
5 Runtime error 279 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Correct 134 ms 239096 KB Output is correct
7 Correct 171 ms 244216 KB Output is correct
8 Correct 281 ms 260468 KB Output is correct
9 Runtime error 308 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 357 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 326 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Execution timed out 1116 ms 248184 KB Time limit exceeded
13 Execution timed out 1100 ms 253296 KB Time limit exceeded
14 Execution timed out 1113 ms 252748 KB Time limit exceeded
15 Runtime error 336 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 341 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 498 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Execution timed out 1109 ms 254688 KB Time limit exceeded

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1109 ms 245608 KB Time limit exceeded
2 Runtime error 273 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 242 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Execution timed out 1101 ms 243016 KB Time limit exceeded
5 Runtime error 230 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Execution timed out 1110 ms 250096 KB Time limit exceeded
7 Execution timed out 1114 ms 245608 KB Time limit exceeded
8 Execution timed out 1109 ms 246392 KB Time limit exceeded
9 Runtime error 241 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 247 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 224 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Execution timed out 1107 ms 247284 KB Time limit exceeded
13 Execution timed out 1104 ms 245100 KB Time limit exceeded
14 Execution timed out 1102 ms 243052 KB Time limit exceeded
15 Runtime error 230 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 251 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Execution timed out 1105 ms 246884 KB Time limit exceeded
18 Runtime error 276 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 241 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 226 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 232 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Execution timed out 1096 ms 246304 KB Time limit exceeded
5 Runtime error 264 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Execution timed out 1101 ms 247520 KB Time limit exceeded
7 Runtime error 251 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 229 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 238 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Execution timed out 1108 ms 244560 KB Time limit exceeded
11 Execution timed out 1104 ms 244072 KB Time limit exceeded
12 Execution timed out 1105 ms 245476 KB Time limit exceeded
13 Runtime error 222 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 386 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Execution timed out 1104 ms 245732 KB Time limit exceeded
16 Execution timed out 1105 ms 245092 KB Time limit exceeded
17 Runtime error 231 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 227 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Execution timed out 1109 ms 251236 KB Time limit exceeded
20 Runtime error 229 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Runtime error 516 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Runtime error 255 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Execution timed out 1105 ms 251876 KB Time limit exceeded
24 Execution timed out 1107 ms 242920 KB Time limit exceeded
25 Execution timed out 1103 ms 245900 KB Time limit exceeded
26 Execution timed out 1107 ms 246472 KB Time limit exceeded
27 Runtime error 257 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
28 Execution timed out 1097 ms 247532 KB Time limit exceeded
29 Runtime error 247 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Runtime error 230 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Execution timed out 1103 ms 244844 KB Time limit exceeded
32 Execution timed out 1104 ms 244208 KB Time limit exceeded
33 Execution timed out 1108 ms 241524 KB Time limit exceeded
34 Runtime error 256 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
35 Execution timed out 1106 ms 244328 KB Time limit exceeded
36 Runtime error 263 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
37 Runtime error 266 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
38 Execution timed out 1108 ms 247528 KB Time limit exceeded
39 Execution timed out 1102 ms 242292 KB Time limit exceeded
40 Execution timed out 1102 ms 248168 KB Time limit exceeded
41 Runtime error 242 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
42 Execution timed out 1113 ms 246884 KB Time limit exceeded