oj.uz

답안 #251981

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
251981 2020-07-23T12:01:07 Z abacaba Brunhilda’s Birthday (BOI13_brunhilda) C++14
80.3175 / 100
 621 ms 80504 KB 
#include <bits/stdc++.h>
using namespace std;
 
template <typename T> void Min(T &a, T b) {
    a = min(a, b);
}
 
template <typename T> void Max(T &a, T b) {
    a = max(a, b);
}

const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int N = 1e7 + 15;
int n, m, q, k, a[N];
int mx[N], dp[N];

main() {
    memset(dp, 0x3f, sizeof(dp));
    ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
    cin >> m >> q;
    while(m--) {
        int p;
        cin >> p;
        for(int i = p - 1; i < N; i += p)
            Max(mx[i], p - 1);
    }
    for(int i = N - 2; i; --i)
        Max(mx[i], mx[i + 1] - 1);
    dp[0] = 0;
    for(int i = 1; i < N; ++i)
        Min(dp[i], dp[i - mx[i]] + 1);
    while(q--) {
        int x;
        cin >> x;
        if(dp[x] == inf)
            cout << "oo" << endl;
        else
            cout << dp[x] << endl;
    }
    return 0;
}

Compilation message

brunhilda.cpp:18:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 78584 KB Output is correct
2 Correct 130 ms 78580 KB Output is correct
3 Correct 131 ms 78584 KB Output is correct
4 Correct 140 ms 78712 KB Output is correct
5 Correct 120 ms 78584 KB Output is correct
6 Correct 111 ms 78584 KB Output is correct
7 Correct 117 ms 78584 KB Output is correct
8 Correct 125 ms 78584 KB Output is correct
9 Correct 139 ms 78584 KB Output is correct
10 Correct 156 ms 78612 KB Output is correct
11 Correct 148 ms 78584 KB Output is correct
12 Correct 113 ms 78708 KB Output is correct
13 Correct 239 ms 78680 KB Output is correct
14 Correct 274 ms 78840 KB Output is correct
15 Correct 141 ms 78716 KB Output is correct
16 Correct 137 ms 78584 KB Output is correct
17 Correct 148 ms 78692 KB Output is correct
18 Correct 148 ms 78712 KB Output is correct

Subtask #2
18.8888888889 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 153 ms 78712 KB Output is correct
2 Correct 158 ms 79352 KB Output is correct
3 Correct 311 ms 79196 KB Output is correct
4 Correct 150 ms 78804 KB Output is correct
5 Correct 223 ms 78968 KB Output is correct
6 Correct 130 ms 78588 KB Output is correct
7 Correct 126 ms 78840 KB Output is correct
8 Correct 153 ms 78736 KB Output is correct
9 Correct 259 ms 79068 KB Output is correct
10 Correct 316 ms 79228 KB Output is correct
11 Incorrect 309 ms 78968 KB Output isn't correct
12 Correct 202 ms 78792 KB Output is correct
13 Correct 118 ms 78584 KB Output is correct
14 Correct 166 ms 78756 KB Output is correct
15 Correct 253 ms 78968 KB Output is correct
16 Correct 149 ms 79352 KB Output is correct
17 Correct 253 ms 78840 KB Output is correct
18 Correct 259 ms 79484 KB Output is correct

Subtask #3
41.4285714286 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 350 ms 79352 KB Output is correct
2 Correct 350 ms 79224 KB Output is correct
3 Correct 410 ms 79608 KB Output is correct
4 Incorrect 361 ms 79736 KB Output isn't correct
5 Incorrect 366 ms 80376 KB Output isn't correct
6 Correct 477 ms 79608 KB Output is correct
7 Correct 355 ms 79864 KB Output is correct
8 Correct 317 ms 79352 KB Output is correct
9 Correct 324 ms 79352 KB Output is correct
10 Correct 257 ms 78840 KB Output is correct
11 Incorrect 247 ms 78840 KB Output isn't correct
12 Correct 327 ms 78968 KB Output is correct
13 Correct 505 ms 79864 KB Output is correct
14 Correct 366 ms 79992 KB Output is correct
15 Incorrect 282 ms 78968 KB Output isn't correct
16 Correct 297 ms 78968 KB Output is correct
17 Correct 275 ms 79124 KB Output is correct
18 Correct 343 ms 79224 KB Output is correct
19 Incorrect 166 ms 78840 KB Output isn't correct
20 Correct 393 ms 79608 KB Output is correct
21 Incorrect 387 ms 79992 KB Output isn't correct
22 Correct 514 ms 80408 KB Output is correct
23 Correct 372 ms 79864 KB Output is correct
24 Correct 360 ms 79608 KB Output is correct
25 Correct 422 ms 79712 KB Output is correct
26 Incorrect 377 ms 79612 KB Output isn't correct
27 Correct 541 ms 79824 KB Output is correct
28 Incorrect 473 ms 79740 KB Output isn't correct
29 Correct 621 ms 80248 KB Output is correct
30 Correct 540 ms 80248 KB Output is correct
31 Correct 327 ms 79740 KB Output is correct
32 Incorrect 360 ms 79688 KB Output isn't correct
33 Incorrect 302 ms 79608 KB Output isn't correct
34 Correct 335 ms 79952 KB Output is correct
35 Incorrect 331 ms 79736 KB Output isn't correct
36 Correct 555 ms 80376 KB Output is correct
37 Incorrect 376 ms 80504 KB Output isn't correct
38 Correct 441 ms 79736 KB Output is correct
39 Incorrect 349 ms 79864 KB Output isn't correct
40 Correct 423 ms 79736 KB Output is correct
41 Correct 333 ms 79992 KB Output is correct
42 Correct 490 ms 80124 KB Output is correct