Submission #1109673

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1109673	2024-11-07T09:24:46 Z	qrn	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	40 / 100	1000 ms	1352 KB

brunhilda

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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