oj.uz

답안 #1109673

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1109673 2024-11-07T09:24:46 Z qrn Brunhilda’s Birthday (BOI13_brunhilda) C++14
40 / 100
 1000 ms 1352 KB 
#include <bits/stdc++.h>
using namespace std;

#define SPEED ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);


#define int long long
#define endl "\n"
#define ALL(X) X.begin(), X.end()

const int sz = 10005, inf = 1e9;

vector<int>dp(sz);

int f(vector<int> &a, int w) {
    int t = 0;
    for(int i = 0; i < (int)a.size(); i++) {
        t = max(t, (w % a[i]));
    }
    if(t == 0) t = -1;
    return t;
}

void solve() {
    int m, q;
    cin >> m >> q;
    vector<int> a(m);
    for(int i = 0; i < m; i++) cin >> a[i];
    if(q == 1) {
        int ans = 0;
        int qq;
        cin >> qq;
        bool cock = false;
        while(qq > 0) {
            int tmp = f(a, qq);
            if(tmp == -1) {
                cock = true;
                break;
            }
            qq -= tmp;
            ans++;
        }
        if(cock) {
            cout << "oo" << endl;
        } else {
            cout << ans << endl;
        }  
    } else {
        dp[0] = 0;
        for(int i = 1; i < sz; i++) dp[i] = inf;
        for(int i = 1; i < sz; i++) {
            int mini = inf;
            for(int j = 0; j < m; j++) {
                mini = min(mini, dp[i - (i % a[j])]);
            }
            dp[i] = mini + 1;   
        }
        while(q--) {
            int qq;
            cin >> qq;
            // for(int i = 1; i <= 10; i++) {
            //     cout << dp[i] << " ";
            // }
            // cout << endl;

            if(dp[qq] == inf + 1) {
                cout << "oo" << endl;
            } else {
                cout << dp[qq] << endl;
            }
        }
    }
}

signed main() {
    SPEED;
    int tst = 1;
    // cin >> tst;
    while(tst--) {
        solve();
    }
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 4 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 516 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 1 ms 540 KB Output is correct
12 Correct 3 ms 336 KB Output is correct
13 Correct 24 ms 336 KB Output is correct
14 Correct 26 ms 336 KB Output is correct
15 Correct 2 ms 336 KB Output is correct
16 Correct 2 ms 504 KB Output is correct
17 Correct 3 ms 336 KB Output is correct
18 Correct 4 ms 336 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 592 KB Output is correct
2 Correct 7 ms 1104 KB Output is correct
3 Correct 6 ms 848 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 4 ms 848 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 6 ms 860 KB Output is correct
10 Correct 5 ms 848 KB Output is correct
11 Correct 5 ms 848 KB Output is correct
12 Correct 2 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 2 ms 336 KB Output is correct
15 Correct 4 ms 848 KB Output is correct
16 Correct 7 ms 1104 KB Output is correct
17 Correct 3 ms 336 KB Output is correct
18 Correct 8 ms 1104 KB Output is correct

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1060 ms 848 KB Time limit exceeded
2 Execution timed out 1031 ms 848 KB Time limit exceeded
3 Execution timed out 1057 ms 848 KB Time limit exceeded
4 Runtime error 79 ms 552 KB Execution killed with signal 11
5 Execution timed out 1062 ms 1104 KB Time limit exceeded
6 Runtime error 188 ms 840 KB Execution killed with signal 11
7 Execution timed out 1070 ms 1104 KB Time limit exceeded
8 Execution timed out 1062 ms 848 KB Time limit exceeded
9 Execution timed out 1055 ms 848 KB Time limit exceeded
10 Runtime error 139 ms 840 KB Execution killed with signal 11
11 Runtime error 103 ms 584 KB Execution killed with signal 11
12 Runtime error 137 ms 840 KB Execution killed with signal 11
13 Runtime error 691 ms 1024 KB Execution killed with signal 11
14 Runtime error 2 ms 592 KB Execution killed with signal 11
15 Runtime error 128 ms 820 KB Execution killed with signal 11
16 Runtime error 165 ms 836 KB Execution killed with signal 11
17 Execution timed out 1047 ms 1352 KB Time limit exceeded
18 Execution timed out 1057 ms 848 KB Time limit exceeded
19 Runtime error 118 ms 824 KB Execution killed with signal 11
20 Execution timed out 1069 ms 848 KB Time limit exceeded
21 Runtime error 4 ms 592 KB Execution killed with signal 11
22 Execution timed out 1085 ms 1076 KB Time limit exceeded
23 Runtime error 691 ms 1096 KB Execution killed with signal 11
24 Runtime error 27 ms 536 KB Execution killed with signal 11
25 Runtime error 68 ms 600 KB Execution killed with signal 11
26 Runtime error 80 ms 588 KB Execution killed with signal 11
27 Execution timed out 1047 ms 1104 KB Time limit exceeded
28 Runtime error 24 ms 592 KB Execution killed with signal 11
29 Execution timed out 1066 ms 1104 KB Time limit exceeded
30 Execution timed out 1077 ms 848 KB Time limit exceeded
31 Runtime error 103 ms 584 KB Execution killed with signal 11
32 Runtime error 68 ms 544 KB Execution killed with signal 11
33 Runtime error 30 ms 592 KB Execution killed with signal 11
34 Execution timed out 1083 ms 1104 KB Time limit exceeded
35 Runtime error 48 ms 584 KB Execution killed with signal 11
36 Execution timed out 1083 ms 1104 KB Time limit exceeded
37 Execution timed out 1068 ms 1104 KB Time limit exceeded
38 Runtime error 188 ms 844 KB Execution killed with signal 11
39 Runtime error 54 ms 584 KB Execution killed with signal 11
40 Runtime error 219 ms 852 KB Execution killed with signal 11
41 Execution timed out 1069 ms 1104 KB Time limit exceeded
42 Runtime error 70 ms 584 KB Execution killed with signal 11